Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor linear P let Γ(Adj) be the set of queries {β ≥ γ, γ ≥β} over all adjacent β, γ ∈PSOP. Then Γ(Adj) is a CompSymA-questionnaire for P containing only simple neces- sary queries, and MQS(P; CompSymA) = |Γ′|, where Γ′ is any equivalence-reduced version of Γ(Adj).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite menu \(A\subseteq\mathbb{Q}^p\), a rational polytope \(W\subseteq\mathbb{R}^p\), and a distribution \(\mu\) over the distinct weak-order types \(T\) induced by \(W\), choose a batch \(\Gamma\) of symmetric pairwise-comparison queries and a decoder. Every answer pattern consistent with a type \(t\in T\) must decode to an alternative optimal for \(t\); minimize the per-capita query load \(\sum_{q\in\Gamma}\sum_{t\in T}\mu_t=|\Gamma|\).
Given a nonempty menu \(A\subseteq\mathbb{Q}^p\), with \(m=|A|\) and \(p\geq1\), and a nonempty rational polytope \(W\subseteq\mathbb{R}^p\) specified by \(h\) rational weak inequalities, define preferences by \(\alpha\succeq_w\beta\iff w\cdot\alpha\geq w\cdot\beta\). Coordinates and weights may have either sign; weights need not be normalized.
A society is given by its support: a list \(T\) of \(\tau\) distinct weak orders realized by weights in \(W\), each with positive binary rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). The support may omit realized types; \(\tau\) counts supported types, not all possible types. Each type is explicitly listed as ordered indifference classes.
A symmetric query between distinct \(\alpha,\beta\in A\) has answers \(\alpha\succeq\beta\) and \(\beta\succeq\alpha\). Either answer is allowed when they tie, independently across queries.
A batch \(\Gamma\) is a set of such queries asked of everyone. A decoder assigns one alternative to each answer pattern; for every \(t\in T\), every pattern whose answers hold in \(t\) must decode to a top-ranked alternative in \(t\). No explicit decoder table is part of the input.
Minimize the per-capita load \(\sum_{q\in\Gamma}\sum_{t\in T}\mu_t=|\Gamma|\). The decision input also contains a nonnegative binary integer budget \(k\); \(L\) is the total input bit length.
Is deciding whether a valid batch and decoder exist with \(|\Gamma|\leq k\) solvable in polynomial time in \(m,\tau,p,h,L\), or is it \(\mathrm{NP}\)-hard?
For the full preference family realized by a convex polytope, a minimum symmetric batch consists of comparisons between adjacent potentially uniquely optimal alternatives, identifying alternatives tied throughout the polytope and merging queries with identical unordered answer sets; adjacency means their optimality regions intersect in dimension \(\dim(W)-1\). [Wilson](https://journals.sagepub.com/doi/full/10.3233/FAIA250847).
The author suggests polynomial-time computation for that full-family setting, without proving a complexity theorem. No classification for the arbitrary supported-subfamily problem above was located.
The decision problem is \(\mathrm{NP}\)-hard, even when all supported preferences are strict orders, all supported types have distinct unique winners, all masses are equal, the alternatives are standard-basis vectors, and the weight polytope is a rational box.
The proof is a polynomial-time many-one reduction from Set Cover. It accounts for every available comparison, including comparisons other than those intended to encode sets.
Suppose every supported type \(t\) is a strict order with unique top alternative \(a_t\). For a batch \(\Gamma\), let \(P_\Gamma(t)\) denote its unique answer pattern. Strictness makes this pattern unique because exactly one answer holds for each query.
Lemma. A valid decoder exists if and only if
\(P_\Gamma(t)=P_\Gamma(t')\) implies \(a_t=a_{t'}\).
Proof. A pattern shared by two types must decode to an alternative optimal in both. Since their optimal alternatives are unique, those alternatives must coincide.
Conversely, if the stated condition holds, assign each realized pattern the common winner of the types producing it. Assign any alternative to unrealized patterns. This defines a valid decoder. \(\square\)
Consequently, when supported types have distinct unique winners, a valid batch is exactly a batch that gives distinct patterns to all supported types.
We use the classical \(\mathrm{NP}\)-completeness of Set Cover. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Write its instance as a universe \(U=\{1,\ldots,n\}\), sets \(S_1,\ldots,S_s\subseteq U\), and a nonnegative integer budget \(b\). The question is whether at most \(b\) sets cover \(U\).
We may restrict to \(n\geq1\) and \(\bigcup_{j=1}^{s}S_j=U\). This restriction preserves hardness: an empty universe is immediately a yes-instance, and an uncovered element immediately gives a no-instance; either can be replaced by a fixed instance satisfying the restriction and having the same answer.
Set \(r=n+3\). Introduce the following labels, which will index supported preference types:
Let \(Z\) be this label set. Its cardinality is \(N=2n+2r=4n+6\).
We now define \(r+s\) binary tests on \(Z\).
Let \(E_1,\ldots,E_r\) be the standard-basis vectors of \(\mathbb{R}^r\). Define the cyclic successor by \(\sigma(i)=i+1\) for \(i<r\), and \(\sigma(r)=1\).
Assign each label an identifier vector \(\xi(z)\in\{0,1\}^r\):
\(\xi(g_i^0)=E_{\sigma(i)},\qquad \xi(g_i^1)=E_{\sigma(i)}+E_i.\)
\(\xi(u_e^0)=\xi(u_e^1)=E_1+E_2+E_{e+3}.\)
Identifier test \(I_i\) returns coordinate \(\xi_i(z)\).
These vectors have three useful properties.
For the third property, guard identifiers have Hamming weight one or two. The weight-one identifiers are distinct because \(\sigma\) is a permutation. The weight-two identifiers are distinct because their supports are the distinct edges \(\{i,\sigma(i)\}\) of a cycle of length \(r\geq4\). Element identifiers have weight three, with distinct third coordinates \(e+3\), so they differ from every guard identifier and from those of other elements.
For each \(j\in\{1,\ldots,s\}\), define test \(F_j\) by
\(F_j(g_i^0)=F_j(g_i^1)=0,\qquad F_j(u_e^0)=0,\qquad F_j(u_e^1)=\mathbf{1}_{\{e\in S_j\}}.\)
Thus \(F_j\) separates element pair \(\{u_e^0,u_e^1\}\) exactly when \(e\in S_j\), and separates no guard pair.
Let \(d=r+s\), and enumerate all tests as \(B_1,\ldots,B_d\), with identifiers first and set tests second.
Fix an enumeration \(Z=\{z_1,\ldots,z_N\}\). Introduce alternatives
\(C=\{c_1,\ldots,c_N\},\qquad D=\{x_\ell,y_\ell:1\leq\ell\leq d\}.\)
The menu is \(A=C\cup D\), with
\(m=N+2d=6n+2s+12.\)
For the supported type indexed by \(z_a\), define the following strict order:
All supported types are distinct, and their unique winners are distinct. By the lemma, validity is equivalent to distinguishing all labels in \(Z\).
Every query has one of the following four forms.
Within one test block. Comparing \(x_\ell\) with \(y_\ell\) implements exactly test \(B_\ell\), with answer \(y_\ell\succeq x_\ell\) representing value one.
Between different test blocks. Every supported type ranks the earlier block above the later block. The answer is constant.
Between \(C\) and \(D\). Every supported type ranks every alternative in \(C\) above every alternative in \(D\). The answer is constant.
Within \(C\). Consider \(c_a,c_b\) with \(a<b\). In type \(z_b\), \(c_b\) is the winner, so \(c_b\succ c_a\). In every other type, \(c_a\succ c_b\): this follows either because \(c_a\) is the winner or because the remaining alternatives in \(C\) follow increasing index order.
Hence this query implements the singleton test that returns one exactly on label \(z_b\).
Therefore every informative query implements either an identifier test, a set test, or a singleton test. There are no additional informative comparison forms.
The constructed orders satisfy the task’s linear-preference requirement.
Set \(p=m\), and assign each alternative a different standard-basis vector of \(\mathbb{Q}^m\). Choose
\(W=[0,m]^m,\)
specified by the \(h=2m\) rational weak inequalities \(0\leq w_a\leq m\).
For any constructed strict order, assign utility \(m\) to its first alternative, utility \(m-1\) to its second, and so on, down to utility one for its last alternative. Let the corresponding vector of utilities be \(w\).
This vector lies in \(W\). Since each alternative is a standard-basis vector, its dot product with \(w\) equals its assigned utility. Thus \(w\) realizes the specified strict order.
Give each supported type mass \(\mu_t=1/N\). These are positive binary-encoded rational numbers summing to one.
Finally, set the batch budget to \(K=r+b\).
The vectors, inequalities, orders, masses, and budget all have polynomial encoding length in the Set Cover input.
Suppose a collection indexed by \(J\subseteq\{1,\ldots,s\}\) covers \(U\), with \(|J|\leq b\).
Choose the comparisons implementing all \(r\) identifier tests and the set tests \(F_j\) for \(j\in J\). This batch has size at most \(r+b=K\).
The identifier answers distinguish every guard label from every other label. They also distinguish labels belonging to different element pairs. The only labels not distinguished by identifiers are \(u_e^0,u_e^1\) within the same element pair.
For each \(e\in U\), the cover contains some \(S_j\) with \(e\in S_j\). The selected test \(F_j\) distinguishes that pair.
Therefore every supported type has a distinct answer pattern. The lemma supplies a valid decoder.
Suppose a valid batch \(\Gamma\) satisfies \(|\Gamma|\leq r+b\). Because all supported types have distinct winners, \(\Gamma\) must distinguish all their labels.
Call a query guard-separating if it separates at least one designated guard pair \(\{g_i^0,g_i^1\}\). Let \(\Gamma_G\) be the set of such queries in \(\Gamma\).
The exhaustive classification gives the following facts:
In particular, each query separates at most one guard pair. Since all \(r\) guard pairs must be separated,
\(|\Gamma_G|\geq r.\)
Moreover, no guard-separating query separates an element pair. For identifier queries this follows from the equal identifiers within each element pair. For singleton queries, a guard-separating singleton isolates a guard label, so both labels of every element pair receive the other answer.
It follows that every element pair must be separated by a query in \(\Gamma\setminus\Gamma_G\), and
\(|\Gamma\setminus\Gamma_G|=|\Gamma|-|\Gamma_G|\leq b.\)
We convert these remaining queries into at most \(b\) covering sets:
To verify coverage, fix \(e\in U\). Some query in \(\Gamma\setminus\Gamma_G\) separates \(u_e^0\) from \(u_e^1\). By the classification, that query is either \(F_j\) with \(e\in S_j\), or a singleton isolating one of those two labels. In either case, its associated set contains \(e\).
The associated sets therefore cover \(U\). After removing duplicates, there are at most \(|\Gamma\setminus\Gamma_G|\leq b\) sets.
This proves the reverse implication.
We have established the equivalence:
\(\text{Set Cover has a cover of size at most }b \quad\Longleftrightarrow\quad \text{the constructed instance has a valid batch of size at most }r+b.\)
The construction is polynomial, so the problem in the question is \(\mathrm{NP}\)-hard. Consequently, a polynomial-time algorithm in \(m,\tau,p,h,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The restriction to strict supported orders is also in \(\mathrm{NP}\): a certificate lists the chosen comparisons, and their deterministic answer patterns can be checked for conflicting winners in polynomial time. The certificate has polynomial length because a batch contains at most \(\binom{m}{2}\) queries. Thus that restriction is \(\mathrm{NP}\)-complete. No membership claim for the general tied-order problem is needed for the requested hardness conclusion.
The polytope in this reduction realizes many orders outside the support. Correctness is required only for the explicitly supported types, so this hardness result concerns a different requirement from [Wilson’s full-family setting](https://journals.sagepub.com/doi/full/10.3233/FAIA250847).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes the requested \(\mathrm{NP}\)-hardness for the arbitrary supported-subfamily problem. Every substantive step is valid, including the treatment of comparisons outside the intended test blocks. No major or minor mathematical issues were found.
Under strict preferences, each type produces exactly one answer pattern and has exactly one optimal alternative. Therefore a shared pattern can satisfy two types precisely when their winners coincide.
The converse correctly defines the decoder on patterns produced by supported types and assigns arbitrary alternatives to all remaining patterns. This is legitimate because the menu is nonempty and unsupported patterns impose no requirements. No explicit decoder table is needed.
Consequently, distinct unique winners make validity equivalent to distinguishing every pair of supported types.
The invoked theorem is that deciding whether an explicitly given finite set family covers its universe using at most the specified budget is \(\mathrm{NP}\)-complete. This is the Set Cover problem covered by [Karp’s completeness theorem](https://studylib.net/doc/27985824/karp1972).
The restrictions to a nonempty universe and a family whose union equals the universe preserve hardness as stated: excluded instances have immediately determined answers and can be replaced by fixed instances of the appropriate answer satisfying both restrictions. Allowing a nonnegative binary budget creates no difficulty.
The counts are correct:
\[
r=n+3,\qquad N=2n+2r=4n+6.
\]
Because \(n\geq1\), the cycle length satisfies \(r\geq4\). Thus the two coordinates in each guard identifier of weight two are distinct, and the unordered cycle edges are distinct.
Each guard pair differs in exactly its designated coordinate. Every element pair has identical identifiers. Guard identifiers have weight one or two, whereas element identifiers have weight three, with distinct third coordinates ranging from \(4\) through \(r\). These facts establish every claimed identifier distinction, including the boundary case \(n=1\).
The set tests have exactly the claimed behavior on designated pairs: they separate an element pair precisely when its element belongs to the corresponding set and separate no guard pair.
Each prescribed order includes every alternative exactly once and is strict. Its unique winner is the alternative indexed by its label, so all supported types are distinct and have distinct winners.
The menu size calculation is correct:
\[
m=N+2(r+s)=6n+2s+12.
\]
The comparison classification exhausts all unordered pairs of distinct alternatives:
The proof does not require every possible singleton test to be available. Classifying every available comparison suffices.
Assigning alternatives distinct standard-basis vectors gives a rational, nonempty menu in dimension \(p=m\). The box
\[
W=[0,m]^m
\]
is a nonempty rational polytope described by \(h=2m\) weak inequalities.
The utilities \(m,m-1,\ldots,1\) lie in this box and are distinct. Their dot products with the standard-basis alternatives realize precisely the specified strict orders.
The masses \(1/N\) are positive rationals with polynomial binary encoding length and sum to one. “Binary-encoded rational” does not require a terminating binary expansion.
The construction has polynomial output size: there are \(N\) explicitly listed orders of length \(m\), and the coordinates and inequalities also have polynomial total size. The binary encoding of \(K=r+b\) remains polynomial even when \(b\) is large.
All identifier queries distinguish guard labels from every other label and distinguish different element pairs. Their only remaining collisions are the two labels within each element pair.
A selected covering set supplies a set query separating each such pair. Therefore every supported type has a distinct pattern, and the decoder lemma applies. The batch uses at most \(r+b\) comparisons.
Distinct winners require every designated guard pair to be separated. The classification shows that each query separates at most one guard pair, hence
\[
|\Gamma_G|\geq r.
\]
Every guard-separating query separates no element pair: identifier tests are equal within element pairs, and guard singleton tests are constant on element labels. Thus all element pairs must be separated by the remaining queries, whose number satisfies
\[
|\Gamma\setminus\Gamma_G|\leq b.
\]
Each remaining query separating an element pair is either a set test containing that element or a singleton isolating one of its labels. The stipulated union condition ensures that the latter can be associated with a set containing that element.
Each query contributes at most one set. Every element receives coverage from a query separating its pair, and removing duplicate sets cannot destroy coverage. This proves the reverse implication without assuming that the batch contains all identifier queries.
The polynomial construction and both implications establish \(\mathrm{NP}\)-hardness for the requested problem. The additional strict-order membership claim is also valid: a polynomial-length comparison certificate determines patterns directly, and conflicting winners can be checked in polynomial time.
The argument correctly limits its \(\mathrm{NP}\)-completeness claim to strict supported orders. Its hardness conclusion for the general problem needs no membership result for tied orders.
Orders realized by the box but omitted from the support impose no decoder constraints under the task’s definition. Accordingly, the reduction addresses the intended supported-subfamily problem and does not rely on Wilson’s full-family result.
Repair feedback: None 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.