Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions; polynomial-time solvable iff \(\mathrm{P}=\mathrm{NP}\); \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, and under polynomial-time many-one reductions iff \(\mathrm{NP}=\mathrm{coNP}\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe OPTTEST problem is coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an issue set \(I\), a finite-support distribution \(\mu\) over compact P-trees on \(I\), a proposed bundle \(M^\star \in CD(I)\), and a rational threshold \(q \in [0,1]\), decide whether \(\sum_{T:\,M^\star \in \operatorname{Opt}(T)} \mu_T \ge q\).
Let \(I\) be a finite set of \(m\) binary issues, and let \(CD(I)\) be its complete truth assignments.
A compact P-tree is a finite rooted tree with arbitrary explicitly encoded propositional formulas over \(I\) labeling internal nodes. Each internal node has either ordered left and right children or one child representing two identical subtrees; recursively duplicating these single-child subtrees defines its full binary expansion.
An outcome follows the left branch when it satisfies the node formula and the right branch otherwise. Outcomes reaching the same expanded leaf are tied; leaves earlier in left-to-right order are strictly preferred. Empty leaves are allowed. Define \(\operatorname{Opt}(T)\) as the outcomes with no strictly preferred outcome in \(CD(I)\).
A society is given by its support: the list of the \(\tau\) compact P-tree types with positive mass, each mass \(\mu_T\) a binary rational, with \(\sum_T\mu_T=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains \(M^\star\in CD(I)\) and a binary rational \(q\in[0,1]\). The decision problem asks whether \(\sum_{T:\,M^\star\in\operatorname{Opt}(T)}\mu_T\ge q\). Let \(L\) be the total input bit length, including compact trees, formula labels, masses, and threshold; state running times in \(m,\tau,L\).
Is this mass-threshold decision problem solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
For a single compact P-tree, testing whether a specified outcome is optimal is \(\mathrm{coNP}\)-complete ([source](https://cdn.aaai.org/ocs/ws/ws1208/8790-38003-1-PB.pdf)). No result for exactly the mass-threshold problem was located in the literature search.
The mass-threshold decision problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, even when \(\tau=1\) and the tree has only one internal node.
Consequently:
Thus, the proposed dichotomy needs a reduction convention: the unconditional many-one classification is \(\mathrm{coNP}\)-completeness.
The supplied paper establishes the single-tree result in Theorem 5. [Liu and Truszczynski, *Preference Trees*](https://cdn.aaai.org/ocs/ws/ws1208/8790-38003-1-PB.pdf). Below is a self-contained proof for the exact mass-threshold problem.
Write \(N\succ_T M\) when the expanded leaf reached by \(N\) precedes the expanded leaf reached by \(M\).
Lemma. Given a compact tree \(T\) and two outcomes \(N,M\), their preference comparison is computable in polynomial time without constructing the full expansion.
Proof. Start at the compact root and evaluate its formula under both outcomes.
If the truth values differ, the outcome satisfying the formula enters the expanded left subtree, and the other enters the expanded right subtree. Every leaf of the former precedes every leaf of the latter, so the preference comparison is determined immediately.
This also applies to a single-child node: its expansion contains two distinct copies of its child subtree, with every leaf of the left copy preceding every leaf of the right copy.
If the truth values agree, both outcomes enter the same expanded child. Continue with the corresponding compact child; at a single-child node, continue with its unique child.
If a leaf is reached without a disagreement, both outcomes reach the same expanded leaf and are tied. These cases exhaust all possibilities and prove correctness.
Let \(\ell_T\) be the encoded length of \(T\), including its formulas. With indexed access to assignment bits, formula evaluation along the path takes \(O(\ell_T)\) time. Including assignment handling gives the conservative bound \(O(m+\ell_T)\). In particular, formula sizes must be counted; tree height alone is insufficient. \(\square\)
Index the support by \(T_1,\ldots,T_\tau\), with masses \(\mu_1,\ldots,\mu_\tau\). Define
\(B=\{i:M^\star\notin\operatorname{Opt}(T_i)\}\).
Since the masses sum to one, the instance is a no-instance exactly when
\(\displaystyle \sum_{i\in B}\mu_i>1-q.\)
A certificate for a no-instance consists of a subset \(S\subseteq\{1,\ldots,\tau\}\) and, for each \(i\in S\), an outcome \(N_i\in CD(I)\). The verifier checks
\(N_i\succ_{T_i}M^\star\quad\text{for every }i\in S,\)
and
\(\displaystyle \sum_{i\in S}\mu_i>1-q.\)
Soundness. Every verified preference comparison proves \(i\in B\), so \(S\subseteq B\). Positivity of the masses then gives
\(\displaystyle \sum_{i\in B}\mu_i\ge\sum_{i\in S}\mu_i>1-q.\)
Hence the optimality mass is strictly below \(q\).
Completeness. For any no-instance, take \(S=B\). By the definition of nonoptimality, each \(i\in B\) admits an outcome \(N_i\succ_{T_i}M^\star\). The strict mass inequality holds because the instance is a no-instance.
The certificate contains at most \(\tau\) assignments, so its length is \(O(\tau m+\tau)\) using a support bitmap. Since both \(m\) and \(\tau\) are bounded by the explicitly encoded input length \(L\), this is polynomial in \(L\).
Write \(\mu_i=a_i/b_i\) and \(q=c/d\), with positive denominators, and set
\(\displaystyle D=d\prod_{i=1}^{\tau}b_i.\)
The bit length of \(D\) is \(O(L)\), because the sum of the input denominator lengths is at most \(L\). Set
\(W_i=a_i(D/b_i),\qquad Q=c(D/d).\)
Then the certificate’s mass test is the exact integer comparison
\(\displaystyle \sum_{i\in S}W_i>D-Q.\)
All these integers have \(O(L)\) bits: validity of the input gives \(\sum_iW_i=D\) and \(0\le Q\le D\). Schoolbook multiplication and division compute them in \(O((\tau+1)L^2)\) bit operations.
By the lemma, all certificate comparisons together take \(O(\tau m+L)\) time with indexed assignment access. Thus certificate verification takes
\(O\!\left(\tau m+L+(\tau+1)L^2\right),\)
which is polynomial in \(L\). The complement belongs to \(\mathrm{NP}\), proving that the decision problem belongs to \(\mathrm{coNP}\).
Reduce from propositional unsatisfiability, which is \(\mathrm{coNP}\)-complete.
Given a formula \(\varphi\) over issues \(x_1,\ldots,x_n\), introduce a fresh issue \(z\). Construct a tree \(T_\varphi\) with one internal node, labeled
\(z\land\varphi,\)
and two leaf children. Let \(M^\star\) assign every issue false, and use the society
\(\tau=1,\qquad \mu_{T_\varphi}=1,\qquad q=1.\)
The construction has polynomial size. Since \(M^\star(z)=0\), the specified outcome reaches the right leaf.
If \(\varphi\) is satisfiable, extend a satisfying assignment by setting \(z=1\). This outcome reaches the left leaf and is strictly preferred to \(M^\star\). The optimality mass is therefore zero, and the constructed instance answers no.
If \(\varphi\) is unsatisfiable, the root formula is false under every outcome. The left leaf is empty, and every outcome reaches the right leaf. All outcomes are tied and optimal. The optimality mass is one, and the constructed instance answers yes.
Therefore,
\(\varphi\text{ is unsatisfiable}\iff\text{the constructed mass-threshold instance answers yes}.\)
This proves \(\mathrm{coNP}\)-hardness. Together with Section 2, it establishes \(\mathrm{coNP}\)-completeness.
The same reduction works for any fixed threshold satisfying \(0<q\le1\). At \(q=0\), every valid instance answers yes.
An unconditional algorithm enumerates all \(2^m\) outcomes. For every support tree, it records whether any enumerated outcome is strictly preferred to \(M^\star\). After enumeration, the unmarked trees are exactly those for which \(M^\star\) is optimal.
Using the comparison lemma and the exact arithmetic above, its running time is
\(O\!\left(2^m(\tau m+L)+(\tau+1)L^2\right),\)
with indexed assignment access and bit costs charged for rational arithmetic. Standard Turing-machine simulation adds only polynomial overhead. The algorithm never constructs expanded trees. In particular, it is polynomial in \(L\) for fixed \(m\); fixing \(\tau\) alone does not remove hardness.
Finally, let \(A\) denote this decision problem.
If \(A\in\mathrm{P}\), the reduction from unsatisfiability yields a polynomial-time unsatisfiability algorithm. Complementing its answer gives a polynomial-time satisfiability algorithm, implying \(\mathrm{P}=\mathrm{NP}\). Conversely, \(\mathrm{P}=\mathrm{NP}\) implies \(\mathrm{coNP}=\mathrm{P}\), hence \(A\in\mathrm{P}\).
For Turing hardness, the construction in Section 3 lets a satisfiability algorithm query \(A\) once and negate the answer. Since satisfiability is \(\mathrm{NP}\)-complete, \(A\) is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions.
For many-one hardness, if \(A\) were \(\mathrm{NP}\)-hard, satisfiability would many-one reduce to \(A\in\mathrm{coNP}\). Closure of \(\mathrm{coNP}\) under polynomial-time preimages would place satisfiability in \(\mathrm{coNP}\), implying \(\mathrm{NP}=\mathrm{coNP}\). Conversely, that equality would make the proved \(\mathrm{coNP}\)-hardness also \(\mathrm{NP}\)-hardness.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The mass-threshold problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. The distinction between many-one and Turing \(\mathrm{NP}\)-hardness is necessary and correctly explained. I found no major or minor mathematical gaps.
Until the first formula on which the two outcomes disagree, both outcomes follow the same path in the full expansion. Agreement at a single-child node means they enter the same expanded copy; continuing through its unique compact child therefore preserves this invariant.
At the first disagreement, the satisfying outcome enters the left subtree and the other enters the right subtree. Every expanded leaf of the left subtree precedes every expanded leaf of the right subtree, including when these subtrees are identical copies. Subsequent formula evaluations cannot reverse this comparison.
If there is no disagreement before reaching a leaf, both outcomes reach the same expanded leaf and are tied. Empty leaves introduce no exception because the compared outcomes actually reach their respective leaves.
The bound \(O(m+\ell_T)\) is justified under the stated indexed-access model: the traversed formulas and nodes occupy at most the entire compact encoding. The proof correctly includes formula lengths rather than counting only tree height.
For \(B=\{i:M^\star\notin\operatorname{Opt}(T_i)\}\), normalization gives optimality mass \(1-\sum_{i\in B}\mu_i\). Consequently, a no-instance is characterized exactly by
\(\sum_{i\in B}\mu_i>1-q\).
The strict inequality correctly handles equality at the threshold.
Soundness holds: every accepted witness establishes membership in \(B\), and positive masses ensure that the mass of a certified subset cannot exceed the mass of \(B\).
Completeness holds: nonoptimality is defined by the existence of a strictly preferred outcome, so each member of \(B\) has the required witness. Choosing \(S=B\) supplies a certificate for every no-instance. The argument does not require the verifier to establish optimality for any omitted tree.
A support bitmap together with at most \(\tau\) complete assignments uses \(O(\tau m+\tau)\) bits. The explicitly encoded support and specified assignment ensure that \(\tau\) and \(m\) are bounded by the input length \(L\).
The common denominator \(D=d\prod_i b_i\) has \(O(L)\) bits because its logarithm is bounded by the sum of the encoded denominator lengths. The divisions defining \(W_i\) and \(Q\) are exact.
On valid inputs, \(\sum_iW_i=D\), \(0\le Q\le D\), and all relevant partial sums lie between zero and \(D\). Thus the integer comparison is exact and uses only \(O(L)\)-bit integers. The stated schoolbook arithmetic bound covers the multiplications, divisions, additions, and comparison.
Combining this with the compact-tree comparisons justifies the verification bound
\(O(\tau m+L+(\tau+1)L^2)\).
Therefore the complement belongs to \(\mathrm{NP}\), as claimed.
The constructed instance satisfies the task’s requirements: its formula is explicitly encoded, its tree has one internal node and two leaves, its sole mass is positive and sums to one, and its threshold is valid. Introducing a fresh issue and writing the all-false assignment requires polynomial size.
Since \(M^\star(z)=0\), the specified outcome always reaches the right leaf. If \(\varphi\) is satisfiable, a satisfying assignment extended with \(z=1\) reaches the preferred left leaf, making \(M^\star\) nonoptimal.
If \(\varphi\) is unsatisfiable, every outcome reaches the right leaf and is optimal. The empty left leaf is explicitly permitted by the task.
Hence the reduction preserves yes-instances of unsatisfiability exactly. It establishes \(\mathrm{coNP}\)-hardness even for \(\tau=1\) and one internal node. Together with membership, this establishes completeness.
The reduction produces optimality mass either zero or one, so it works for every fixed threshold \(0<q\le1\). At \(q=0\), every valid instance answers yes.
The certificate argument also covers \(q=1\), ties, trees consisting of a single leaf, and \(m=0\). None requires an additional assumption or lemma.
Enumerating every outcome supplies every possible witness of nonoptimality. Thus the unmarked trees after enumeration are precisely those for which \(M^\star\) is optimal.
Summing the comparison costs over the support gives the stated bound
\(O(2^m(\tau m+L)+(\tau+1)L^2)\)
under the explicitly stated indexed-access model. The qualification concerning polynomial overhead for Turing-machine simulation is appropriate. Fixed \(m\) makes this polynomial in \(L\); fixed \(\tau\) alone does not remove the proved hardness.
The arguments establishing polynomial-time solvability iff \(\mathrm{P}=\mathrm{NP}\), Turing \(\mathrm{NP}\)-hardness, and many-one \(\mathrm{NP}\)-hardness iff \(\mathrm{NP}=\mathrm{coNP}\) all follow correctly from the proved completeness result and the stated closure property.
The cited [paper’s Theorem 5](https://cdn.aaai.org/ocs/ws/ws1208/8790-38003-1-PB.pdf) does classify specified-outcome optimality testing as \(\mathrm{coNP}\)-complete under matching compact-tree semantics. Its omitted reduction details do not leave a gap here: the prover supplies an independent reduction for the exact target problem.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.