d4-conf-ijcai-2016-0015 (d4-conf-ijcai-2016-0015)

Given a finite alternative set \(\mathcal A\), integer-valued evaluations \(\mathcal C\), addition, and a finitely supported rational distribution \(\mu\) over contributor types \(P\), where each \(P\) is a packet of strict and non-strict comparisons, decide whether there is a hierarchy \(H=(C_1,\ldots,C_k)\) with \(|C_i|\le 2\) that satisfies every comparison in every packet with \(\mu_P>0\).

Given a finite alternative set \(\mathcal A\) with \(m=|\mathcal A|\), let \(\mathcal C\) contain \(n\geq2\) evaluation functions \(c:\mathcal A\to\mathbb Z_{\geq0}\), supplied as binary tables; smaller values are preferred.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational \(\mu_P>0\), with \(\sum_P\mu_P=1\). Here \(\tau\) is the support size, not the number of possible types. Each type \(P\) is an explicitly listed finite packet of statements \(\alpha<\beta\) or \(\alpha\leq\beta\), with \(\alpha,\beta\in\mathcal A\).
A hierarchy \(H=(C_1,\ldots,C_k)\) is an ordered partition of any subset of \(\mathcal C\), with \(1\leq|C_i|\leq2\); evaluations may be omitted, and \(H=()\) is allowed.
Define \(v_H(\alpha)=(\sum_{c\in C_1}c(\alpha),\ldots,\sum_{c\in C_k}c(\alpha))\). A strict statement requires \(v_H(\alpha)<_{\mathrm{lex}}v_H(\beta)\); a non-strict statement requires \(v_H(\alpha)\leq_{\mathrm{lex}}v_H(\beta)\). Equal vectors remain tied, including all pairs under the empty hierarchy.
The decision problem asks whether one hierarchy satisfies every statement in every supported packet. Let \(g=\sum_P|P|\) and let \(L\) be the total input bit length; state running times in \(m,n,\tau,g,L\).

Is this distributional hierarchy-consistency problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For a finite statement set, any singleton hierarchy of maximum length satisfying the non-strict versions can be the initial sequence of a satisfying hierarchy whenever one exists. [Verified structural result](https://arxiv.org/html/2410.23934v1).
Finite-set consistency is NP-complete with addition and levels of size at most two; singleton-only consistency is polynomial. [Verified complexity results](https://arxiv.org/html/2409.11044v1). No result explicitly treating the stated distributional input was located.

The problem is \(\mathrm{NP}\)-complete, already with support size \(\tau=1\) and evaluation values in \(\{0,1\}\).

1. Flattening the supported packets

Let
\[ \Gamma=\bigcup_{P:\mu_P>0}P. \]

For every admissible hierarchy \(H\),
\[ H\text{ satisfies every supported packet} \quad\Longleftrightarrow\quad H\text{ satisfies every statement in }\Gamma. \]

Indeed, both conditions require satisfaction of exactly the statements appearing in at least one supported packet. Repeated occurrences impose no additional requirement. The positive masses therefore have no effect on the answer.

Concatenating the packet lists takes \(\mathrm O(L)\) time and produces \(g\) statement occurrences. Deduplication is unnecessary. In particular, this conversion does not enumerate any unsupported types.

If all statements are non-strict, the empty hierarchy satisfies them all. That special case is always a yes-instance. The hardness below concerns the permitted mixture of strict and non-strict statements.

2. Membership in \(\mathrm{NP}\)

A certificate lists the selected evaluation indices in order, together with boundaries specifying levels of size one or two. Because evaluations cannot repeat, it contains at most \(n\) indices and has length \(\mathrm O(n\log(n+1))\).

First verify that all indices are valid and distinct and that each level has the required size. For each statement \(\alpha\mathrel{\triangleleft}\beta\), scan the levels in order and compute
\[ d_i=\sum_{c\in C_i}c(\alpha)-\sum_{c\in C_i}c(\beta). \]

The first nonzero \(d_i\) determines the lexicographic comparison:

• If \(d_i<0\), either kind of statement is satisfied.
• If \(d_i>0\), either kind is violated.
• If every \(d_i=0\), the non-strict statement is satisfied and the strict statement is violated.

These rules follow directly from the definition of lexicographic order, including the empty hierarchy.

There are at most \(gn\) level checks. If the largest table entry has \(b\) bits, each level sum has at most \(b+1\) bits because a level contains at most two evaluations. Thus binary encoding causes no exponential arithmetic cost.

For definiteness, a conservative bound for reading the input and verifying a certificate is
\[ T_{\mathrm{ver}} =\mathrm O\!\left((mn+\tau+n^2+gn+1)L^2\right) \]
bit operations. This allows straightforward sequential table access and pairwise checks for repeated indices; it is not intended to be tight. All parameters are bounded by the explicit input length, so verification is polynomial in \(L\). Therefore the problem belongs to \(\mathrm{NP}\).

3. Hardness with one supported packet

The finite-set hardness result applies to addition, ordered partitions of subsets of the evaluations, and levels of size at most two. More specifically, its Section 3 construction produces nonnegative integer tables using only \(\{0,1\}\), non-strict statements \(\Gamma_0\), and alternatives \(a,b\), such that a given \(\mathrm{3SAT}\) instance is satisfiable exactly when an admissible hierarchy satisfies \(\Gamma_0\cup\{b<a\}\). Its construction has at least two evaluations. These are precisely the hierarchy and comparison conventions here. See [Wilson, George, and O’Sullivan, Section 3, Proposition 2](https://arxiv.org/html/2409.11044v1).

Map that finite-set instance to a society with the single supported packet
\[ P=\Gamma_0\cup\{b<a\}, \qquad \mu_P=1. \]

Keep the alternative set and evaluation tables unchanged. This is a polynomial-time many-one reduction: it merely packages the statement list and adds a constant-size rational mass.

By Section 1, the resulting society admits a satisfying hierarchy exactly when the finite-set instance does. Hence the distributional problem is \(\mathrm{NP}\)-hard, even when \(\tau=1\), all entries belong to \(\{0,1\}\), and there is exactly one strict statement.

Together with Section 2, this proves \(\mathrm{NP}\)-completeness.

4. Why the singleton-prefix result does not imply tractability

The supplied [singleton-prefix structural result](https://arxiv.org/html/2410.23934v1) guarantees a possible initial sequence. That sequence can be empty even when pair levels are essential.

Consider evaluations \(a,b\) given by:

| Evaluation | \(x\) | \(y\) | \(z\) | \(t\) |
|---|---:|---:|---:|---:|
| \(a\) | \(0\) | \(1\) | \(0\) | \(1\) |
| \(b\) | \(1\) | \(0\) | \(0\) | \(0\) |

Require \(x\leq y\), \(y\leq x\), and \(z<t\).

Any nonempty singleton hierarchy begins with \(a\) or \(b\). Beginning with \(a\) violates \(y\leq x\); beginning with \(b\) violates \(x\leq y\). Consequently, the maximum-length singleton hierarchy satisfying the non-strict versions is empty.

Nevertheless, \(H=(\{a,b\})\) satisfies the original statements: its sums tie \(x\) and \(y\) at \(1\), while the sums at \(z,t\) are respectively \(0,1\). Thus the structural result leaves a substantive pair-level search problem.

5. An explicit general running-time bound

Exhaustive enumeration gives a deterministic decision algorithm. For each \(r\leq n\), enumerate ordered lists of \(r\) distinct evaluations and all divisions into consecutive blocks of size one or two. Include \(r=0\).

There are at most \(n^r\) lists and at most \(2^r\) divisions, so the total number examined is
\[ \sum_{r=0}^{n}(2n)^r=\mathrm O((2n)^n). \]

Using the verifier above gives the explicit upper bound
\[ \mathrm O\!\left( (2n)^n(mn+\tau+n^2+gn+1)L^2 \right). \]

A polynomial-time algorithm for the general problem exists if and only if \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the assigned problem correctly: it establishes \(\mathrm{NP}\)-completeness, including hardness with support size \(\tau=1\), evaluation values in \(\{0,1\}\), and exactly one strict statement. No major or minor mathematical issues were found.

Step-by-step verification

1. Flattening supported packets

The equivalence is correct for every admissible hierarchy \(H\). Both sides require the same hierarchy to satisfy every statement occurring in any supported packet. There is no probabilistic threshold or packet-dependent choice of hierarchy in the task.

Repeated statements do not change satisfaction. Since the input explicitly lists only supported types, concatenation requires no enumeration of other types. Its claimed \(\mathrm O(L)\) cost is valid, and retaining all \(g\) occurrences is sufficient.

The observation about non-strict instances is also correct: under \(H=()\), all alternatives have equal vectors, so every non-strict statement holds. This includes empty packets and an empty statement collection.

2. Membership in \(\mathrm{NP}\)

The certificate represents precisely the permitted hierarchies:

• Valid, distinct indices enforce selection of a subset of evaluations.
• Level boundaries enforce sizes one or two.
• The empty certificate represents the allowed empty hierarchy.

At most \(n\) evaluation indices are needed, giving the stated \(\mathrm O(n\log(n+1))\) certificate length.

The comparison procedure is correct. For each statement, the first nonzero difference determines lexicographic order; if no difference is nonzero, the alternatives remain tied. Thus strict and non-strict statements are handled correctly, including self-comparisons and the empty hierarchy.

The arithmetic bound is valid: adding at most two nonnegative \(b\)-bit entries produces a sum with at most \(b+1\) bits. Signed subtraction also requires only linear bit length.

There are at most \(gn\) level checks. The conservative verification bound
\[ \mathrm O\!\left((mn+\tau+n^2+gn+1)L^2\right) \]
accommodates input reading, sequential table access, arithmetic, and duplicate-index checks. Under the explicit input representation, it is polynomial in \(L\). The proof establishes membership in \(\mathrm{NP}\).

3. Hardness and the cited theorem

The citation supports the precise restricted hardness statement used. The source defines models as ordered partitions of possibly empty subsets, uses the same strict and non-strict lexicographic comparisons, and permits levels of size at most two when its parameter is set to two. Section 3 uses only zero-one table entries and non-strict input statements. Proposition 2 identifies satisfiability with failure of a non-strict entailment, equivalently existence of a model satisfying those statements and one reverse strict statement. The construction on nonempty-variable instances meets \(n\geq2\). These hypotheses match the task. [Wilson, George, and O’Sullivan, Section 3 and Proposition 2](https://arxiv.org/html/2409.11044v1).

The subsequent packaging reduction is correct. A single packet containing the finite statement set, with mass \(1\), is a valid society. It preserves all tables and hierarchy restrictions and adds only polynomial encoding overhead.

By the already established flattening equivalence, the reduction preserves both yes-instances and no-instances. Hence the claimed restricted \(\mathrm{NP}\)-hardness follows. Together with membership, this proves \(\mathrm{NP}\)-completeness.

4. Singleton-prefix discussion

The cited structural result concerns a singleton hierarchy satisfying the non-strict versions and having maximum length. Its use here is consistent with Proposition 4.3; addition satisfies the strict monotonicity assumption used in that section. [Singleton-prefix result](https://arxiv.org/html/2410.23934v1).

The example’s calculations are correct:

• Starting with evaluation \(a\) gives \(a(y)=1>0=a(x)\), violating \(y\leq x\).
• Starting with evaluation \(b\) gives \(b(x)=1>0=b(y)\), violating \(x\leq y\).
• Consequently, no nonempty singleton hierarchy satisfies even those two non-strict requirements.
• The pair level gives equal sums \(1\) at \(x,y\), and sums \(0,1\) at \(z,t\), satisfying all original statements.

Thus the example correctly demonstrates that the guaranteed singleton prefix can be empty while a pair level is necessary.

5. Exhaustive running-time bound

Every admissible hierarchy can be represented by an ordered list of its selected evaluations divided into consecutive blocks of size one or two. Enumeration may represent some hierarchies repeatedly, which does not affect correctness.

For each \(r\), the bounds \(n^r\) on lists and \(2^r\) on divisions are valid upper bounds. Including \(r=0\) covers the empty hierarchy.

Since \(n\geq2\), the geometric sum is uniformly \(\mathrm O((2n)^n)\). Multiplication by the conservative verifier bound gives the stated deterministic running time in \(m,n,\tau,g,L\).

The final equivalence between a polynomial-time algorithm and \(\mathrm P=\mathrm{NP}\) follows from the established \(\mathrm{NP}\)-completeness.

Actionable feedback

No mathematical repair or additional clarification is required. The cited theorem is sufficiently identified, its relevant hypotheses match the task, and the computational bounds are valid.

⟨structured verdict parsed — rendered above⟩