Answer: —
Theorem 15 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven optimization problems $P$ and $Q$, deciding $P\equiv^{s} Q$ is $\CONP$-complete in case of CO-problems and $\PiP{2}$-complete in case of ASO-problems.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix a finite atom set \(U\), choose CO or ASO semantics, and let each type \(\theta\) be a complete module \(P_\theta=(G_\theta,S_\theta)\). Given finite-support rational distributions \(\mu,\nu\) over types, form \(P_\mu=(\bigcup_{\mu_\theta>0}G_\theta,\bigcup_{\mu_\theta>0}S_\theta)\) and \(P_\nu\) analogously. Decide whether \(\operatorname{Opt}(P_\mu\cup(\emptyset,S_R))=\operatorname{Opt}(P_\nu\cup(\emptyset,S_R))\) for every ranked selector \(S_R\), where \(\operatorname{Opt}\) is the set of preferred outcomes under the chosen semantics.
Let \(U\) be an input atom set with \(m=|U|\), and choose CO or ASO semantics. A type is a module \(P_\theta=(G_\theta,S_\theta)\), with a finite propositional theory \(G_\theta\) and a finite set \(S_\theta\) of preference rules over \(U\); empty components and inconsistent generators are allowed.
A rule \(r\) has the form \(\phi_1>\cdots>\phi_k\xleftarrow{j}\psi\), where \(k,j\geq1\), ranks are binary integers, and all formulas are explicitly represented propositional formulas. For \(I\subseteq U\), set \(v_I(r)=\min\{\ell:I\models\phi_\ell\}\) when \(I\models\psi\) and some head formula holds; otherwise set \(v_I(r)=1\). Selector formulas are evaluated classically under both semantics.
For a selector \(S\), \(I>^S J\) holds when, at the smallest rank containing any rule with unequal satisfaction degrees, every rule weakly favors \(I\) and at least one strictly favors \(I\). If no degree differs, neither interpretation strictly dominates the other.
For \(P=(G,S)\), outcomes are the classical models of \(G\) under CO and its equilibrium models under ASO. Define \(\operatorname{Opt}(P)\) as the outcomes undominated by another outcome under \(>^S\). Module union is componentwise set union.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; masses sum to \(1\). Support size counts listed types, not possible types. For two societies, let \(\tau\) be the larger support size and \(L\) the total input bit length, including modules, ranks, and masses; state running times in \(m,\tau,L\).
Given societies \(\mu,\nu\), define \(P_\mu=(\bigcup_{\mu_\theta>0}G_\theta,\bigcup_{\mu_\theta>0}S_\theta)\) and analogously \(P_\nu\). Decide whether \(\operatorname{Opt}(P_\mu\cup(\emptyset,S_R))=\operatorname{Opt}(P_\nu\cup(\emptyset,S_R))\) for every finite selector \(S_R\) over \(U\), with arbitrary positive integer ranks.
For each of CO and ASO semantics, is this distribution decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For explicit module pairs, this selector-extension equivalence problem is \(\mathrm{coNP}\)-complete under CO and \(\Pi_2^P\)-complete under ASO, already with simple input selectors. These results use exactly the module semantics and unrestricted selector contexts defined above.
Under polynomial-time many-one reductions, the distribution problems are:
| Semantics | Complexity | Consequence |
|---|---|---|
| CO | \(\mathrm{coNP}\)-complete | It is \(\mathrm{NP}\)-hard if and only if \(\mathrm{NP}=\mathrm{coNP}\). |
| ASO | \(\Pi_2^P\)-complete | It is \(\mathrm{NP}\)-hard. |
Thus the proposed “in \(\mathrm P\) or \(\mathrm{NP}\)-hard” dichotomy needs qualification for CO. Under polynomial-time Turing reductions, both problems are \(\mathrm{NP}\)-hard.
I prove these classifications and an explicit deterministic running-time bound below. The classifications are complete; the requested unconditional CO dichotomy under many-one reductions remains dependent on open complexity-class equalities.
Given societies \(\mu,\nu\), form their aggregate modules \(P_\mu,P_\nu\) by taking the prescribed unions. Their combined representation has length \(O(L)\), because every constituent formula and rule already occurs in the input. Duplicate elimination, if needed, takes \(O(L^2)\) time by direct comparisons.
The resulting explicit-module instance asks exactly the same question as the society instance. The atom set remains \(U\), and masses have no further role once the positive support is specified.
Conversely, given any explicit modules \(P,Q\), construct two singleton societies:
These are valid societies, their aggregates are \(P,Q\), and their support sizes are both \(1\). The transformation has linear output length and preserves the answer.
Consequently, for each semantics, the society problem and the supplied explicit-module problem are polynomial-time many-one equivalent. Applying the completeness results stated in the question proves:
Both hardness results already hold for \(\tau=1\), with the same simple input selectors as in the supplied results.
This section supplies a direct algorithm without enumerating selector contexts.
For a selector \(S\) and distinct interpretations \(I,J\), define \(d_S(I,J)\) as the smallest rank at which some rule has unequal degrees on \(I,J\). Set \(d_S(I,J)=\infty\) if no such rule exists.
When \(d_S(I,J)\) is finite, define \(T_S(I,J)\) to contain:
Thus \(T_S(I,J)\) is one of \(\{+\},\{-\},\{+,-\}\). When \(d_S(I,J)=\infty\), set \(T_S(I,J)=\emptyset\).
Write \(F_S(I,J)=(d_S(I,J),T_S(I,J))\).
Proposition. Let \(P=(G_P,S_P)\) and \(Q=(G_Q,S_Q)\), using either CO or ASO semantics. They have equal optimal outcomes under every selector extension if and only if:
Fix any extension \(R\) and any distinct \(I,J\in D\).
At each rank, adjoining rules combines the signs contributed by the original selector and by \(R\). Let \(d\) be the original first differing rank, and let \(e\) be the extension’s first differing rank.
If \(e<d\), the extension determines the comparison. If \(d<e\), the original selector determines it. If \(d=e\), their sign sets are united. The same reasoning applies when either rank is \(\infty\).
Therefore the original fingerprint and \(R\) completely determine the extended comparison. Equal fingerprints imply identical strict-dominance relations on \(D\). An interpretation is optimal precisely when no member of \(D\) strictly dominates it, so the optimal sets are equal.
For every atom \(a\in U\), put both rules \(a>\neg a\xleftarrow{1}\top\) and \(\neg a>a\xleftarrow{1}\top\) into an extension \(R_0\).
Any distinct interpretations differ on some atom. Its two rules contribute opposite signs at rank \(1\), making the interpretations incomparable regardless of the original selector. Hence every outcome is optimal after adding \(R_0\).
Equality under this extension forces equality of the outcome sets. When \(U=\emptyset\), there is at most one interpretation, so every outcome is already optimal and the same conclusion follows.
Suppose the common outcome set is \(D\), and fix distinct \(I,J\in D\).
For \(K\subseteq U\), let \(\delta_K\) be the conjunction specifying exactly \(K\): it contains \(a\) for \(a\in K\) and \(\neg a\) for \(a\notin K\). Set \(A=\delta_I\lor\delta_J\).
Add the rank-\(1\) rules \(A>\neg A\xleftarrow{1}\top\) and \(\neg A>A\xleftarrow{1}\top\).
These rules give identical degrees to \(I,J\), so they do not alter their comparison. Between either of them and any interpretation outside \(\{I,J\}\), however, they contribute opposite signs. Consequently, no outside outcome can dominate \(I\) or \(J\), even after further rules are added. Their optimality is therefore determined solely by their mutual comparison.
Suppose their fingerprints differ.
If their first differing ranks coincide, they are finite and their sign sets differ. The three sign sets yield, respectively, the optimal subsets \(\{I\}\), \(\{J\}\), and \(\{I,J\}\) within this isolated pair. Thus the extended optimal sets differ.
Otherwise, interchange \(P,Q\) if necessary so that \(d_{S_P}(I,J)<d_{S_Q}(I,J)\). Write \(d=d_{S_P}(I,J)\).
In the first case, the added rule contributes \(-\); in the other cases it contributes \(+\). Under \(P\), the resulting first-rank sign set is \(\{+,-\}\), so both interpretations are optimal within the pair. Under \(Q\), the added rule is the first differing rule and creates strict dominance, so only one is optimal.
The isolating rules exclude interference from other outcomes. Therefore differing fingerprints contradict equivalence under every selector extension. This proves the proposition.
The proposition gives a deterministic algorithm with running time \(O(\tau+4^mL^2)\) under either semantics. Here is a conservative bit-operation accounting.
First aggregate the modules in \(O(\tau+L^2)\) time.
Under CO, enumerate the \(2^m\) interpretations and evaluate the generators. This takes \(O(2^mL^2)\) time.
Under ASO, use the defining equilibrium-model test: \(I\) must satisfy the theory at the total here-and-there interpretation \((I,I)\), and no \((H,I)\) with \(H\subsetneq I\) may satisfy it. There are \(3^m\) pairs with \(H\subseteq I\), because each atom is absent from \(I\), belongs to \(I\setminus H\), or belongs to \(H\). Evaluating an explicitly represented formula at its two worlds takes polynomial time, giving the conservative bound \(O(3^mL^2)\).
Compare the resulting outcome sets. If they agree, examine all ordered pairs of distinct outcomes. There are fewer than \(4^m\) such pairs. For each, scan the input selectors to compute and compare their fingerprints, in \(O(L^2)\) time.
Ranks are compared as binary integers; the algorithm never iterates through every integer up to a rank. Thus their numerical magnitude does not introduce an additional exponential factor.
The resulting bound is polynomial in the input length for fixed \(m\), with no exponential dependence on \(\tau\).
For CO, suppose the problem were \(\mathrm{NP}\)-hard. Because it belongs to \(\mathrm{coNP}\), closure of \(\mathrm{coNP}\) under polynomial-time many-one reductions would imply \(\mathrm{NP}\subseteq\mathrm{coNP}\). Taking complements gives the reverse inclusion. Hence \(\mathrm{NP}=\mathrm{coNP}\).
Conversely, if \(\mathrm{NP}=\mathrm{coNP}\), its proved \(\mathrm{coNP}\)-completeness makes it \(\mathrm{NP}\)-hard. Therefore CO is \(\mathrm{NP}\)-hard if and only if \(\mathrm{NP}=\mathrm{coNP}\).
Likewise, its membership in \(\mathrm P\) is equivalent to \(\mathrm P=\mathrm{NP}\): membership would put every \(\mathrm{coNP}\) language, and therefore every \(\mathrm{NP}\) language by complementation, in \(\mathrm P\); the converse follows immediately from \(\mathrm P=\mathrm{NP}=\mathrm{coNP}\).
For ASO, \(\mathrm{NP}\subseteq\Pi_2^P\): an \(\mathrm{NP}\) existential predicate can be written with a preceding universal quantifier whose variable is ignored. Its \(\Pi_2^P\)-completeness therefore implies \(\mathrm{NP}\)-hardness. A polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).
CO is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. Given an \(\mathrm{NP}\) language \(B\), its complement belongs to \(\mathrm{coNP}\) and reduces many-one to the CO problem. Query that instance and negate the answer to decide membership in \(B\).
ASO is already hard under many-one reductions, hence also under Turing reductions.
The remaining open issue concerns only the requested unconditional CO classification under the many-one convention; the society encoding itself introduces no additional complexity.
⟨structured verdict parsed — rendered above⟩
The mathematical argument is correct. It establishes $\mathrm{coNP}$-completeness for CO and $\Pi_2^P$-completeness for ASO, together with the stated deterministic running-time bound. No major or minor mathematical gaps were found.
The qualification concerning CO is necessary: $\mathrm{coNP}$-completeness does not unconditionally imply $\mathrm{NP}$-hardness under polynomial-time many-one reductions. The prover correctly explains this distinction.
Both reductions are valid.
Thus the claimed completeness classifications follow independently of the later finite characterization.
The fingerprint definition correctly records all information relevant to a pairwise comparison:
The extension calculation is correct. If the original selector and extension first differ at ranks $d$ and $e$, respectively, the smaller rank determines the comparison; when the ranks coincide, their sign sets combine.
Componentwise set union does not invalidate this calculation: removing a duplicate rule cannot remove a sign contributed by that rule.
The infinite-rank cases also work. In particular, when both fingerprints have infinite rank, neither selector contributes a difference.
Therefore equal fingerprints on a common outcome set imply equal strict-dominance relations after every selector extension. Equal optimal sets follow directly from the definition of optimality.
The proposed extension $R_0$ is valid and finite.
For an atom on which two interpretations differ, the two opposite rank-$1$ rules have opposite degree comparisons. Their bodies are true, and their heads exhaust the two possible truth values, so the default-degree convention creates no exception.
Since all original ranks are positive, these opposite signs occur at the earliest possible rank. Original rules can add signs but cannot remove either sign. Thus distinct interpretations become incomparable, and every outcome becomes optimal.
Selector extensions leave generators unchanged under both CO and ASO. Equality of optimal sets under this extension therefore forces equality of outcome sets.
The prover explicitly handles $U=\emptyset$: there is at most one interpretation, which is automatically undominated if it is an outcome. Empty outcome sets are also covered.
For distinct $I,J$, the formula $A=\delta_I\lor\delta_J$ holds exactly on the chosen pair.
The two opposite rank-$1$ rules give equal degrees to $I$ and $J$, so they do not change their mutual comparison. Between either chosen interpretation and any outside interpretation, they contribute both signs at rank $1$.
This prevents outside outcomes from dominating either chosen interpretation, even after further rules are added. Their membership in the optimal set consequently depends only on their mutual comparison.
There is no empty-atom ambiguity here: distinct interpretations cannot exist when $U=\emptyset$.
If unequal fingerprints have the same first differing rank, that rank must be finite: infinite rank always has the empty sign set.
The three possible finite sign sets produce exactly the three stated optimal subsets of the isolated pair. Different sign sets therefore distinguish the extended optimal sets.
After swapping the modules if necessary, the assumption $d_{S_P}(I,J)<d_{S_Q}(I,J)$ makes $d=d_{S_P}(I,J)$ finite.
The added rule contributes the claimed sign:
Under $P$, the resulting sign set is $\{+,-\}$ in every listed case. Under $Q$, all original degrees agree through rank $d$, so the added rule supplies a single sign at the first differing rank and creates strict dominance.
The isolation rules remain effective, including when $d=1$. Hence one module makes both chosen interpretations optimal, while the other makes only one optimal.
This establishes necessity and completes the proposition.
The bound $O(\tau+4^mL^2)$ is a valid conservative bound.
Since $2^m\leq4^m$ and $3^m\leq4^m$, the combined bound follows. It is polynomial for fixed $m$, and contains no exponential dependence on $\tau$.
All claimed consequences are correct.
For CO:
For ASO, the inclusion $\mathrm{NP}\subseteq\Pi_2^P$ is correctly justified by an ignored leading universal quantifier. Its completeness therefore implies many-one $\mathrm{NP}$-hardness.
The Turing-hardness argument for CO is also valid: reduce the complement of an $\mathrm{NP}$ language to the CO problem, query the resulting instance, and negate the answer.
The output fully resolves the complexity classification warranted by the supplied results. Its final "claim": "partial" label is overly conservative if interpreted as saying the proof itself is incomplete. The open class equalities concern the requested CO dichotomy, not a gap in the established classification.
No additional mathematical clarification or repair is required.
⟨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.