Answer: Deciding nonemptiness is \(\mathrm{NP}\)-complete, even with one type, universally feasible configurations, and at most two parents per feature. Total output-polynomial enumeration is possible if and only if \(\mathrm{P}=\mathrm{NP}\).
Theorem 4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven a (possibly cyclic) constrained CP-net ⟨N, C⟩an outcome is feasible and approximately optimal for ⟨N, C⟩iff it satisfies C ∪opt∗(N, C). It immediately follows that we can test if an outcome is feasible and approximately optimal in polynomial time: we just need to test the satisfiability of the approximate opti- mality constraints. On the other hand, determining if a con- strained CP-net has any feasible and approximately optimal outcomes is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution \(\mu\) over \(\tau\) types, each a complete binary CP-net over the same features and parent contexts, pool each conditional preference by mass-weighted majority, treating ties as indifference, to obtain \(N_\mu\). Given shared hard constraints \(C\), find every feasible configuration for which no other feasible configuration is approximately better under \(N_\mu\), where approximately better means connected to it by a chain of worsening flips whose outcomes all satisfy \(C\).
The input has \(m\geq 1\) Boolean features and common parent sets, each excluding its own feature; the dependency graph may be cyclic. Each type is a complete CP-net with explicitly listed strict conditional orders for every parent assignment.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
For each feature and parent assignment, \(N_\mu\) prefers the value supported by greater total mass; equal masses mean indifference. A worsening flip changes exactly one feature from its strictly preferred value to its less preferred value in the current parent context; indifference permits no worsening flip.
Shared hard constraints \(C\) are given in CNF over these features. Configurations are complete Boolean assignments, and feasibility means satisfying \(C\); feasibility is not promised.
For distinct feasible configurations \(x,y\), write \(x\succ^* y\) when a nonempty chain of worsening flips runs from \(x\) to \(y\), with every configuration, including both endpoints, satisfying \(C\). Let \(S\) contain precisely the feasible \(y\) for which no distinct feasible \(x\) satisfies \(x\succ^* y\), even when reverse reachability also holds.
The task is to enumerate \(S\) without repetitions. Let \(L\) be the total input bit length and \(B\) the total output bit length.
Can every member of \(S\) be enumerated in time polynomial in \(m,\tau,L,B\), or is deciding whether \(S\neq\varnothing\) NP-hard?
For a single constrained, possibly cyclic CP-net, approximately optimal configurations have an exact hard-constraint characterization; checking a supplied configuration is polynomial-time, while existence is NP-complete. [Prestwich et al.](https://cdn.aaai.org/AAAI/2005/AAAI05-073.pdf)
For related finite, unweighted CP-net profiles without hard constraints, existence of a hypercube Condorcet winner under local majority aggregation is NP-complete. [Conitzer et al.](https://www.ijcai.org/Proceedings/11/Papers/038.pdf)
No result treating this exact rational-mass constrained enumeration formulation was located.
1. Result
Deciding whether \(S\neq\varnothing\) is \(\mathrm{NP}\)-complete. Hardness holds even when there is one type of mass \(1\), every assignment is feasible, and every feature has at most two parents.
Consequently, enumeration without repetitions in total time polynomial in \(m,\tau,L,B\) is possible if and only if \(\mathrm{P}=\mathrm{NP}\).
The proof below treats the stipulated definition literally: reverse reachability does not protect a configuration from exclusion.
2. Reachability reduces to a local test
For an assignment \(y\), let \(y^{(i)}\) denote the assignment obtained by complementing feature \(i\).
Lemma. A feasible configuration \(y\) belongs to \(S\) if and only if there is no feasible worsening flip into \(y\).
Proof. An incoming feasible worsening flip \(z\to y\) is itself a nonempty feasible chain from a distinct configuration, so it excludes \(y\) from \(S\).
Conversely, suppose a nonempty feasible worsening chain from a distinct configuration ends at \(y\). Its final step is a worsening flip \(z\to y\), where \(z\) is feasible and differs from \(y\) in exactly one feature. Thus an incoming feasible worsening flip exists. This argument applies equally when reverse reachability holds. \(\square\)
Because a feature is excluded from its own parent set, \(y\) and \(y^{(i)}\) have the same parent context for feature \(i\). Therefore,
\(y^{(i)}\to y\)
is a worsening flip precisely when the aggregate strictly prefers \(1-y_i\) to \(y_i\) in that context. Indifference produces no such edge.
Hence the exact characterization is
\(y\in S\iff C(y)\ \land\ \bigwedge_{i=1}^{m}\left[\neg C\bigl(y^{(i)}\bigr)\ \lor\ \text{the aggregate does not strictly prefer }1-y_i\text{ to }y_i\right].\)
In particular, when every assignment is feasible and all aggregate orders are strict, membership in \(S\) means that every feature currently takes its locally preferred value.
3. Exact rational aggregation and membership in \(\mathrm{NP}\)
Write the positive masses as \(\mu_t=a_t/d_t\), with positive integers \(a_t,d_t\), for \(1\leq t\leq\tau\). Define
\(D=\prod_{t=1}^{\tau}d_t,\qquad w_t=a_t(D/d_t).\)
Then each \(w_t\) is an integer and \(\sum_t w_t=D\). The bit length of \(D\) is at most \(1+\sum_t\log_2 d_t\), hence polynomial in \(L\). Since \(0<w_t\leq D\), the integer weights also have polynomial bit length.
For feature \(i\) and parent assignment \(u\), define the integer majority margin
\(H_i(u)=2\sum_{\{t:\text{type }t\text{ prefers }1\text{ in row }(i,u)\}}w_t-D.\)
The aggregate prefers \(1\) when \(H_i(u)>0\), prefers \(0\) when \(H_i(u)<0\), and is indifferent when \(H_i(u)=0\). These comparisons are exact.
All types use the same parent sets, and every row is explicitly listed. Thus all margins can be computed in polynomial time in \(m,\tau,L\); no implicit exponential table must be expanded.
Given a proposed configuration \(y\), we can:
By the lemma, these checks verify exactly that \(y\in S\). They take polynomial time. A configuration is an \(m\)-bit witness, so deciding \(S\neq\varnothing\) belongs to \(\mathrm{NP}\).
4. Hardness with one type and universally feasible configurations
We give a polynomial reduction from \(\mathrm{3SAT}\). This avoids obtaining hardness merely from the possibility that the hard constraints are infeasible.
Let \(F\) be a Boolean formula in three-literal conjunctive normal form, with variables \(x_1,\ldots,x_n\). Build an acyclic Boolean circuit computing \(F\), using NOT gates and AND/OR gates of fan-in at most two. Binary OR gates compute each clause, and binary AND gates combine the clauses. The circuit has size polynomial in the encoding length of \(F\). Let \(R\) denote its output feature.
We construct a single complete CP-net. Its mass is \(1\). Each preference below specifies the preferred Boolean value; the other value is strictly less preferred.
Input features. For each formula variable, introduce distinct features \(X_j,Y_j\), with parent sets
\(\operatorname{Pa}(X_j)=\{Y_j\},\qquad \operatorname{Pa}(Y_j)=\{X_j\}.\)
Feature \(X_j\) prefers the current value of \(Y_j\), and \(Y_j\) prefers the current value of \(X_j\).
Thus both input features take their preferred values exactly when
\(X_j=Y_j.\)
Either common Boolean value is allowed.
Circuit features. Introduce one feature for every circuit gate. Its parents are the features supplying its inputs. In every parent assignment, it prefers the gate’s Boolean output. For example, an AND feature with parents \(P,Q\) prefers \(P\land Q\).
Each gate has at most two parents. Every gate is a distinct feature, so no parent set contains its own feature. If a gate uses the same signal twice, that signal appears only once in its parent set, and the table evaluates the corresponding gate accordingly.
When all circuit features take their preferred values, induction along the circuit’s topological order gives
\(R=F(X_1,\ldots,X_n).\)
Final two features. Introduce distinct features \(U,V\), with
\(\operatorname{Pa}(U)=\{R,V\},\qquad \operatorname{Pa}(V)=\{U\}.\)
Feature \(V\) prefers \(U\). Feature \(U\) prefers \(V\) when \(R=1\), and prefers \(1-V\) when \(R=0\).
Consequently, their simultaneous preferred-value conditions are
\(V=U,\qquad U=\begin{cases}V,&R=1,\\1-V,&R=0.\end{cases}\)
If \(R=0\), these conditions imply \(U=1-U\), which has no Boolean solution. If \(R=1\), they hold for either common value \(U=V\).
Take the hard constraint CNF to be the tautology \(C=(U\lor\neg U)\). Every configuration is therefore feasible.
Every feature has at most two parents, so each conditional table has at most four rows. Listing all strict orders, parent sets, and the mass \(1\) takes polynomial space and time. With one type, the common-parent-set requirement is automatically satisfied.
Correctness.
Suppose \(F\) has a satisfying assignment \(a\). Set \(X_j=Y_j=a_j\), assign every gate its evaluated circuit value, and set \(U=V=0\). Then \(R=1\), and every feature takes its preferred value. By the local characterization, this configuration belongs to \(S\).
Conversely, suppose \(y\in S\). Every assignment is feasible, and every order is strict. Therefore every feature must take its preferred value. The input features give \(X_j=Y_j\), and the gate conditions give \(R=F(X_1,\ldots,X_n)\). The final two features force \(R=1\). Thus the assignment to the \(X_j\) satisfies \(F\).
We have proved
\(F\text{ is satisfiable}\iff S\neq\varnothing.\)
This is a polynomial many-one reduction, proving \(\mathrm{NP}\)-hardness. Together with membership in \(\mathrm{NP}\), it establishes \(\mathrm{NP}\)-completeness.
5. Consequences for total output time
Suppose an enumeration algorithm always terminates after printing precisely \(S\), without repetitions, and its total running time is bounded by a polynomial \(p(m,\tau,L,B)\).
On an instance with \(S=\varnothing\), the output bit length is \(B=0\), so the algorithm must terminate within
\(T=p(m,\tau,L,0)\)
steps, rounding upward if necessary.
To decide nonemptiness, simulate the enumerator for \(T\) steps:
This decides the \(\mathrm{NP}\)-complete existence problem in polynomial time. Therefore total output-polynomial enumeration implies \(\mathrm{P}=\mathrm{NP}\). The argument does not assume polynomial delay before the first output.
Conversely, assume \(\mathrm{P}=\mathrm{NP}\). For any partial assignment, the question “does this partial assignment extend to a member of \(S\)?” belongs to \(\mathrm{NP}\): guess the remaining bits and apply the polynomial membership test.
Under the assumption, these extension questions can be answered in polynomial time. Traverse the binary assignment tree, exploring a prefix only when it has an extension in \(S\), and print each successful complete assignment. Each assignment has a unique leaf, so there are no repetitions.
If there are \(k\) outputs, every extendible prefix lies on a path to an output. There are at most \((m+1)k\) such prefixes, and at most two tested children per explored internal prefix. When \(k=0\), only the root needs testing. Thus total running time is polynomial in \(m,\tau,L,B\), since printing the configurations contributes at least \(mk\) bits.
6. Relation to the cited characterization
The feasible-chain semantics matches the approximately optimal outcomes studied by [Prestwich et al., Theorem 4](https://cdn.aaai.org/AAAI/2005/AAAI05-073.pdf). The local proof above explicitly covers rational majority weights, ties, and exclusion despite reverse reachability. The hardness proof is independent of the cited reductions and already applies to a singleton support with tautological constraints.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The local characterization, exact aggregation, hardness reduction, and both directions of the enumeration claim are correct. No blocking issues or substantive gaps were found.
The lemma correctly identifies membership in \(S\) with feasibility and absence of a feasible incoming worsening flip.
This argument does not require acyclicity, antisymmetry, or absence of reverse reachability. It therefore respects the task’s explicit treatment of cycles.
The subsequent characterization is also correct. Since feature \(i\) is excluded from its own parent set, \(y\) and \(y^{(i)}\) have identical parent contexts for that feature. Hence an incoming worsening flip exists exactly when \(y^{(i)}\) is feasible and the aggregate strictly prefers its value of feature \(i\). Ties correctly create no incoming flip.
The displayed characterization checks feasibility separately and correctly handles infeasible neighbors. With universally feasible configurations and strict aggregate orders, it reduces to every feature taking its locally preferred value.
The common-denominator calculation is valid:
\[ D=\prod_{t=1}^{\tau}d_t,\qquad w_t=a_t(D/d_t). \]
Each division is exact. Positivity and normalization of the masses imply \(0<w_t\leq D\) and \(\sum_t w_t=D\).
The bound on the bit length of \(D\) is correct. Although its numerical value can be large, its binary representation has length polynomial in the input length. Products, exact divisions, additions, and comparisons on these integers consequently take polynomial time.
The majority margin correctly compares the mass supporting value \(1\) with the complementary mass supporting value \(0\). Its sign implements precisely the task’s strict-majority and tie rules.
Explicitly listed tables and common parent sets justify computing the margins without expanding an implicitly represented table. The membership procedure then checks exactly the conditions of the lemma, using at most \(m+1\) evaluations of the CNF constraints and polynomially many table and arithmetic operations.
Thus an \(m\)-bit configuration is a polynomially verifiable witness for nonemptiness. Membership in \(\mathrm{NP}\) is established.
The reduction correctly encodes satisfiability as simultaneous satisfaction of all local preferred-value conditions.
Input features. The two copy preferences impose \(X_j=Y_j\), while allowing either Boolean value. Neither feature is its own parent. The permitted cyclic dependencies are used legitimately.
Circuit features. Each gate’s preference table imposes its Boolean gate equation. Since the circuit is acyclic, the stated induction establishes that the output feature equals the formula evaluated on the \(X_j\). Feedback through the input pairs does not invalidate induction over the circuit gates.
Repeated gate inputs are handled correctly by treating parent collections as sets. Each gate still has at most two distinct parents and at most four table rows.
Final features. The simultaneous conditions require \(V=U\). When \(R=0\), the additional condition requires \(U=1-U\), which has no Boolean solution. When \(R=1\), either equal assignment to \(U,V\) satisfies both conditions. This gadget therefore correctly forces \(R=1\) in any member of \(S\).
Constraints and encoding. The chosen clause is tautological, so feasibility imposes no restriction. All preferences are strict and complete, the sole mass is a valid rational mass, and the common-parent-set requirement holds automatically for singleton support. The number of features and explicitly listed rows is polynomial in the formula size.
Forward implication. A satisfying formula assignment extends as described to a configuration taking every feature’s preferred value. Universal feasibility and the local characterization place this configuration in \(S\).
Reverse implication. Every configuration in \(S\) must satisfy every preferred-value condition. The circuit equations and final gadget then imply that its \(X_j\) assignment satisfies the formula.
Both implications are valid. The construction establishes the claimed polynomial many-one reduction, including the restrictions of singleton support, universal feasibility, and at most two parents per feature. Together with membership in \(\mathrm{NP}\), it proves \(\mathrm{NP}\)-completeness.
The timeout argument is correct and does not confuse total running time with polynomial delay.
For a fixed enumerator and a fixed polynomial running-time bound, every empty instance must terminate within the bound evaluated at \(B=0\). Simulation up to that bound therefore permits all three stated decisions:
The polynomial bound may be fixed as part of the resulting decision algorithm; it need not be inferred from the enumerator at runtime. Simulation remains polynomial in the input parameters.
Thus the claimed enumeration algorithm would put the established \(\mathrm{NP}\)-complete decision problem in \(\mathrm{P}\).
The prefix-extension question belongs to \(\mathrm{NP}\): its witness is a complete configuration extending the prefix, checked by the established polynomial membership test.
Under the stated assumption, these questions admit a polynomial-time decision procedure. Pruning the binary assignment tree using that procedure enumerates precisely the successful leaves, each once.
The counting bound is correct. Every extendible prefix belongs to a path to an output, so there are at most \((m+1)k\) extendible prefixes for \(k\) outputs. Testing unsuccessful children increases this count by only a constant factor. An empty instance requires only the root test.
Each output contains \(m\) Boolean values, so \(B\geq mk\). Consequently, the traversal and printing costs are polynomial in the required parameters. The converse is established.
The ancillary comparison is accurate for the single constrained CP-net setting. The cited paper defines approximate dominance using worsening chains whose configurations all satisfy the constraints; Theorem 4 characterizes feasible approximately optimal outcomes through its approximate optimality constraints. This matches the feasible-chain semantics relevant here. [Prestwich et al., “Constraint-Based Preferential Optimization”](https://cdn.aaai.org/AAAI/2005/AAAI05-073.pdf)
The prover does not rely on that theorem to establish rational aggregation, treatment of ties, or hardness. Those claims are independently justified in the submitted argument.
No repair or additional clarification is required for the complexity conclusion. The output establishes \(\mathrm{NP}\)-complete nonemptiness and the claimed equivalence between total output-polynomial enumeration and \(\mathrm{P}=\mathrm{NP}\).
The prescribed metadata field called continuous_status is recorded as "hardness" because the adjudicated output establishes exact decision hardness for the supplied formulation.
⟨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.