Answer: \(\mathrm{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard, under promise-preserving polynomial-time reductions.
Proposition 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDOMINANCE in satisfiable CI-nets is PSPACE-complete, even under any of these restrictions: (1) every CI-statement bears on singletons and has no neg- ative preconditions; (2) every CI-statement bears on singletons and has no posi- tive preconditions; (3) every CI-statement is precondition-free.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite goods set \(V\), a finite support \(\mathcal{T}\) of satisfiable CI-net types \(N_t\) over \(V\) with binary-rational masses \(\mu_t\ge 0\) summing to \(1\), bundles \(X,Y\subseteq V\), and a binary-rational threshold \(q\in[0,1]\), decide whether \(\sum_{t:\,X\succ_{N_t}Y}\mu_t\ge q\).
A CI-net on a finite goods set \(V\), with \(m=|V|\), is an explicitly listed finite set of statements \((S^+,S^-,S_1,S_2)\) whose four components are pairwise disjoint subsets of \(V\).
A strict partial order \(\succ\) on \(2^V\) satisfies the net if it contains every comparison \(A\succ B\) with \(A\supsetneq B\), and, for each statement and every \(C\subseteq V\setminus(S^+\cup S^-\cup S_1\cup S_2)\), contains \(C\cup S^+\cup S_1\succ C\cup S^+\cup S_2\).
A net is satisfiable if such an order exists; for a satisfiable net \(N\), let \(\succ_N\) be the intersection of all orders satisfying it. Preferences may be incomplete; no completion or tie-breaking is applied.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here each type is a CI-net \(N_t\), and \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input promises that every \(N_t\) is satisfiable and supplies bundles \(X,Y\subseteq V\) and a binary-rational threshold \(q\in[0,1]\). Decide whether \(\sum_{t:\,X\succ_{N_t}Y}\mu_t\ge q\). Let \(L\) be the total input bit length, including all net statements, masses, bundles and the threshold; state running times in \(m,\tau,L\).
Is this mass-threshold dominance problem solvable in polynomial time, or is it \(\mathrm{NP}\)-hard?
Single-type dominance for satisfiable CI-nets is \(\mathrm{PSPACE}\)-complete, even with singleton compared sets and no negative preconditions, singleton compared sets and no positive preconditions, or no preconditions ([Bouveret–Endriss–Lang](https://www.lamsade.dauphine.fr/~lang/papers/bel09.pdf)).
No result for this exact distributional mass-threshold problem was identified in the literature search.
The problem is \(\mathrm{PSPACE}\)-complete, and therefore \(\mathrm{NP}\)-hard, under polynomial-time reductions that preserve the satisfiability promise. This holds even with two distinct types, equal masses, and the fixed threshold \(q=\tfrac12\).
Consequently, a polynomial-time algorithm exists only if \(\mathrm{P}=\mathrm{PSPACE}\). The boundary case \(q=0\) always answers yes; the hardness concerns positive thresholds.
For a satisfiable net \(N\), define a directed graph \(G_N\) with vertex set \(2^V\). Include the following edges, directed from preferred to less preferred bundles:
Let \(R_N\) be positive-length reachability in this graph.
Lemma. \(R_N=\succ_N\).
Proof. Every satisfying order contains all graph edges. By transitivity, it therefore contains \(R_N\).
The graph is acyclic: a directed cycle would force \(A\succ A\) in every satisfying order, contradicting irreflexivity. Thus \(R_N\) is itself an irreflexive, transitive relation. It contains all statement comparisons. It also contains every strict inclusion comparison, because deleting the goods in \(A\setminus B\) one at a time gives a path from \(A\) to \(B\) whenever \(A\supsetneq B\).
Hence \(R_N\) is a satisfying strict partial order. Since it is contained in every satisfying order and is itself one of those orders, it equals their intersection. \(\square\)
This argument uses the incomplete induced preference relation directly.
The given single-type theorem states that dominance for satisfiable CI-nets is \(\mathrm{PSPACE}\)-complete. Its semantics match those in the question, including strict partial orders and the least satisfying relation. See Proposition 6 of [Bouveret–Endriss–Lang](https://www.lamsade.dauphine.fr/~lang/papers/bel09.pdf).
Given a promised instance \((N,X,Y)\) of single-type dominance, construct a society with:
Its supporting mass is \(1\) if \(X\succ_N Y\), and \(0\) otherwise. Therefore the threshold is met exactly when the source dominance instance answers yes.
The construction is polynomial-time and preserves satisfiability because it leaves the net unchanged. It also preserves each syntactic restriction in the given theorem. Thus the mass-threshold problem is \(\mathrm{PSPACE}\)-hard under each of those restrictions.
The conclusion also holds for an actual mixture of distinct types.
Introduce two fresh goods \(a,b\). On \(V'=V\cup\{a,b\}\), let \(N_0\) contain exactly the original statements, and set
\(N_1=N_0\cup\{(\varnothing,\varnothing,\{a\},\{b\})\}\).
Give each type mass \(\tfrac12\), keep the original queries \(X,Y\subseteq V\), and fix \(q=\tfrac12\).
Satisfiability. Since \(G_N\) is a finite acyclic graph, define \(h(A)\) to be the maximum length of a directed path starting at \(A\). Every original edge \(A\longrightarrow B\) satisfies \(h(A)>h(B)\).
For \(Z\subseteq V'\), define
\(H(Z)=h(Z\cap V)+2\mathbf{1}_{a\in Z}+\mathbf{1}_{b\in Z}\).
The relation \(Z\succ W\) defined by \(H(Z)>H(W)\) is a strict partial order. It satisfies monotonicity: adding original goods strictly increases \(h\), and adding either fresh good increases its positive contribution. Every original statement comparison strictly decreases \(h\) while leaving fresh goods unchanged. The added comparison replacing \(a\) by \(b\) decreases \(H\) by \(1\). Hence this order satisfies both \(N_0\) and \(N_1\).
Preservation of dominance. Starting at \(X\), which contains neither fresh good, a graph path under either net can never introduce a fresh good. Original statements preserve their presence, deletion edges only remove goods, and the added rule requires \(a\) to be present. Thus paths from \(X\) remain entirely inside \(2^V\), where their edges are exactly those of \(G_N\).
By the lemma,
\(X\succ_{N_0}Y\iff X\succ_NY\iff X\succ_{N_1}Y\).
The supporting mass is therefore again either \(0\) or \(1\), giving the required reduction.
The two nets are distinct, all masses are positive, and the added statement respects every restriction listed in the question.
For each type \(t\), determine whether \(Y\) is reachable from \(X\) in \(G_{N_t}\), and add \(\mu_t\) exactly when it is.
A bundle occupies \(m\) bits. Given bundles \(A,B\), adjacency can be tested in \(\operatorname{poly}(m,L)\) time and space by checking a single deletion or scanning the explicitly listed statements.
There are \(2^m\) vertices. For distinct endpoints, reachability, if present, has a simple path of length at most \(2^m-1\).
A deterministic polynomial-space procedure can be given explicitly. Let \(R_k(A,B)\) mean that there is a path of length at most \(2^k\), allowing length zero. Define:
This recurrence is correct by splitting a path after at most \(2^{k-1}\) edges; conversely, concatenate the two paths.
Enumerating \(Z\) sequentially requires only an \(m\)-bit counter. Evaluating \(R_m(X,Y)\) has recursion depth \(m\), using \(O(m^2)\) bits for recursion frames. Handle \(X=Y\) separately: strict dominance is false.
Processing types sequentially therefore gives deterministic bounds of
\(\tau\,2^{O(m^2)}\operatorname{poly}(m,L)\) time and \(\operatorname{poly}(m,L)\) space.
Write each mass as a binary-encoded fraction \(p_t/d_t\). Accumulate the selected masses using
\(n/d+p_t/d_t=(nd_t+p_td)/(dd_t)\).
The accumulated denominator has bit length bounded by the sum of the input denominator lengths, hence \(O(L)\). Every partial sum lies in \([0,1]\), so its numerator also has \(O(L)\) bits. Comparing the accumulated sum with \(q\) by cross multiplication is exact and uses polynomial time and space. Schoolbook arithmetic suffices for an \(O(L^3)\) total arithmetic bound.
Under the explicit input representation, these space bounds are polynomial in the input length. This proves membership in \(\mathrm{PSPACE}\).
Alternatively, search each graph explicitly. From any bundle there are at most \(m\) deletion successors and one successor per applicable statement. A breadth-first search visits at most \(2^m\) bundles.
This yields deterministic time
\(\tau\,2^m\operatorname{poly}(m,L)+O(L^3)\)
and space
\(O(m2^m)+\operatorname{poly}(m,L)\),
reusing the search storage between types.
In particular, for fixed \(m\), the problem is polynomial-time solvable in \(\tau\) and \(L\). For unrestricted \(m\), the hardness and polynomial-space algorithm establish the claimed completeness.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly. It establishes \(\mathrm{PSPACE}\)-completeness under polynomial-time reductions preserving the satisfiability promise, hence \(\mathrm{NP}\)-hardness. The stronger claim involving two distinct types, equal masses, and threshold \(q=\tfrac12\) is also justified.
No major or minor mathematical issues were found.
The graph construction correctly represents the required comparisons. Single-good deletion edges generate every strict inclusion comparison by transitivity, and the statement edges use exactly the contexts permitted by the task.
The satisfiability promise justifies acyclicity: every graph edge belongs to every satisfying order, so a directed cycle would contradict irreflexivity.
Positive-length reachability is transitive and, because the graph is acyclic, irreflexive. The argument establishes both necessary containments:
Therefore its identification with the intersection defining \(\succ_N\) is correct. The proof respects incomplete preferences and introduces no completion or tie-breaking.
The citation is accurate. Proposition 6 states the claimed satisfiable single-type dominance theorem with all three restrictions separately. Definitions 1–5 use the same statement syntax, strict monotonic partial orders, and least satisfying relation as the task. The source also explicitly states that its hardness reductions produce satisfiable nets. Thus the theorem’s hypotheses and promise match the source instances used here. [Bouveret–Endriss–Lang, Definitions 1–5 and Proposition 6](https://www.lamsade.dauphine.fr/~lang/papers/bel09.pdf).
The restrictions are correctly treated as separate hardness cases; the output does not claim hardness for their simultaneous intersection.
The construction is valid:
The supporting mass is exactly \(1\) on source yes-instances and \(0\) on source no-instances. Threshold comparison therefore preserves the answer in both directions.
The construction has polynomial size, preserves satisfiability, and preserves each source restriction. This establishes the claimed hardness for the target promise problem.
Validity of the construction. The fresh goods are outside \(V\). The added statement has pairwise disjoint components, singleton compared sets, and empty positive and negative preconditions. It preserves each applicable source restriction. The nets are distinct, and their two positive masses sum to \(1\).
Satisfiability. The definition of \(h\) is valid because the original graph is finite and acyclic. For every original edge, the longest-path height strictly decreases, as claimed.
The proposed \(H\) consequently decreases along every required comparison:
Thus the numerical comparison relation is an irreflexive, transitive relation satisfying both extended nets. The satisfiability promise is preserved.
Dominance preservation. The invariant concerning fresh goods is correct. Starting at \(X\), neither original rules nor deletion edges can introduce a fresh good. The additional rule cannot apply because \(a\) is absent. Hence every reachable bundle remains in \(2^V\), where the available edges are exactly the original edges.
The asserted equivalences of dominance follow from the previously proved reachability lemma. Both types consequently agree on the query, yielding supporting mass either \(0\) or \(1\). The fixed threshold distinguishes these cases correctly.
Adjacency. With bundles stored as \(m\)-bit vectors and statements explicitly listed, checking a deletion or a statement-generated comparison takes polynomial time and space. A statement determines at most one successor from a given bundle; its context is fixed by that bundle.
Path length. For distinct endpoints, any reachable pair has a simple path with at most \(2^m-1\) edges. The stated bound is correct.
Recursive reachability. The base case correctly recognizes paths of length zero or one. The midpoint recurrence correctly recognizes paths of length at most \(2^k\): the two subpaths each have the prescribed length bound, and zero-length subpaths cover shorter paths.
Taking \(k=m\) suffices. Sequential midpoint enumeration and depth-first recursive evaluation require only polynomial space. The claimed \(O(m^2)\) storage for recursion frames is valid, with polynomial additional workspace for adjacency.
The separate treatment of \(X=Y\) correctly prevents zero-length reachability from being mistaken for strict dominance.
The resulting bounds
\(\tau\,2^{O(m^2)}\operatorname{poly}(m,L)\) time and \(\operatorname{poly}(m,L)\) space are valid.
The fraction-addition formula is correct without requiring fraction reduction.
The accumulated denominator is a product of selected input denominators, so its bit length is bounded by their total encoded length. Each partial sum lies in \([0,1]\), making the accumulated numerator no larger than its denominator. Thus both have \(O(L)\) bits.
Cross multiplication compares the sum with the threshold exactly. Since the support is explicitly listed, the number of additions is \(O(L)\); schoolbook arithmetic supports the stated \(O(L^3)\) total bound.
Processing types sequentially preserves polynomial space. Together with the reduction, this establishes the claimed promise-preserving \(\mathrm{PSPACE}\)-completeness.
The breadth-first-search successor count and vertex count are correct. The claimed time
\(\tau\,2^m\operatorname{poly}(m,L)+O(L^3)\)
and space
\(O(m2^m)+\operatorname{poly}(m,L)\)
allow storage reuse between types and are valid upper bounds.
For fixed \(m\), the algorithm is polynomial in \(\tau\) and \(L\). For unrestricted \(m\), polynomial-time solvability would imply \(\mathrm{P}=\mathrm{PSPACE}\).
The threshold case \(q=0\) always answers yes because supporting mass is nonnegative. Threshold \(q=1\) is covered by exact comparison. Empty bundles, an empty goods set, and empty statement lists introduce no failure in the arguments. Statements forcing self-comparisons are excluded by the satisfiability promise.
No repair or additional clarification is required. The output establishes the target classification and supplies valid running-time bounds in the requested parameters.
⟨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.