Answer: For every fixed nonconstant \(p\), the promised problem is \(\mathrm{NP}\)-complete, even for \(\tau=1\). For every fixed constant \(p\), it is polynomial-time solvable.
Theorem 5 — class: hardness
Given a common binary attribute set \(V\), outcomes \(x,y\in\{0,1\}^{V}\), a finite support \(\{(C_i,\mu_i)\}_{i=1}^{\tau}\) of complete GCP-net types \(C_i=(V,R_i)\) with positive binary-rational masses summing to \(1\), and a rational threshold \(q\), with \(\operatorname{diam}(C_i)\le p(|V|)\) for a fixed polynomial \(p\), compute \(M_\mu(y,x)=\sum_{i=1}^{\tau}\mu_i\mathbf{1}[y\succ_{C_i}x]\), or decide whether \(M_\mu(y,x)\ge q\); incomparable pairs contribute zero.
Let \(m=|V|\ge1\). A GCP-net \(C=(V,R)\) is supplied as an explicit list of rules \(\varphi:\ell>\neg\ell\), where \(\varphi\) is a possibly empty conjunction of literals excluding the variable of \(\ell\). An improving flip changes only that variable from \(\neg\ell\) to \(\ell\) when \(\varphi\) holds.
Write \(y\succ_C x\) when a positive-length sequence of improving flips leads from \(x\) to \(y\); cycles and conflicting rules are permitted. “Complete” means the entire rule list is supplied, without imposing local completeness or consistency.
The preference graph has outcomes \(\{0,1\}^{V}\) as vertices and improving flips as arcs. Its diameter is the maximum shortest directed-path distance, assigning distance zero to unreachable pairs and identical endpoints.
A society is given by its support: the list of \(\tau\ge1\) GCP-net types with positive masses \(\mu_i\) encoded as binary rationals, with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
Fix a positive integer-valued polynomial \(p\). Inputs promise \(\operatorname{diam}(C_i)\le p(m)\) for every type; checking this promise is outside the problem. Given outcomes \(x,y\) and a binary-rational threshold \(q\in[0,1]\), define \(M_\mu(y,x)=\sum_{i=1}^{\tau}\mu_i\mathbf{1}[y\succ_{C_i}x]\). Incomparable pairs contribute zero; mutual dominance contributes to each direction separately. Let \(L\) be the total input bit length, including all rules and rationals.
Is deciding whether \(M_\mu(y,x)\ge q\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, under the stated diameter promise? State running times in \(m,\tau,L\), treating \(p\) as fixed.
Single-net dominance with polynomially bounded diameter is \(\mathrm{NP}\)-complete ([Kronegger, Lackner, Pfandler and Pichler](https://martin.lackner.xyz/publications/kr-minimal.pdf)).
No result for exactly this rational-mass threshold problem was identified in the search.
For every fixed nonconstant positive integer-valued polynomial \(p\), the promised rational-mass threshold problem is \(\mathrm{NP}\)-complete, already for \(\tau=1\), \(\mu_1=1\), and \(q=1\).
If constant polynomials are allowed, there is an exception: for every fixed constant \(p(m)=K\), the problem is polynomial-time solvable. The intended polynomially growing diameter bound therefore gives \(\mathrm{NP}\)-hardness, and a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The cited single-net result is Theorem 5 of [Kronegger, Lackner, Pfandler and Pichler](https://martin.lackner.xyz/publications/kr-minimal.pdf). We give a direct reduction below to establish hardness for every fixed nonconstant \(p\), including bounds with small leading coefficients.
All claims concern promised inputs; no algorithm checks the diameter promise.
Set \(H=p(m)+1\).
If \(x\ne y\) and \(y\succ_C x\), the diameter promise supplies an improving path from \(x\) to \(y\) of length at most \(p(m)\).
If \(x=y\), positive-length dominance requires a closed improving walk. Choose its first arc \(x\to z\). A flip changes a variable, so \(z\ne x\). Since \(x\) is reachable from \(z\), the promise supplies a path from \(z\) to \(x\) of length at most \(p(m)\). Prepending \(x\to z\) gives a positive-length witness of length at most \(H\).
Thus, for either choice of endpoints, every true dominance assertion has a witness containing between \(1\) and \(H\) flips.
A certificate specifies a subset \(S\subseteq\{1,\ldots,\tau\}\) and, for each \(i\in S\), an improving sequence from \(x\) to \(y\) of length between \(1\) and \(H\). The verifier checks all sequences and accepts exactly when \(\sum_{i\in S}\mu_i\ge q\).
A sequence can be encoded by its flipped-variable indices. Starting from \(x\), the verifier determines each flip’s direction and scans the supplied rules to check that some applicable rule sanctions it.
Soundness. Every verified type contributes its mass to \(M_\mu(y,x)\). Because all masses are positive, \(M_\mu(y,x)\ge\sum_{i\in S}\mu_i\ge q\).
Completeness. If \(M_\mu(y,x)\ge q\), choose \(S\) to contain all types satisfying \(y\succ_{C_i}x\). Section 2 provides the required short witnesses. If \(q=0\), the empty subset suffices.
No certificates of non-dominance are needed.
Write \(\mu_i=a_i/b_i\) and \(q=c/d\), with positive denominators. Define \(D=d\prod_{i=1}^{\tau}b_i\). The comparison is equivalent to the integer inequality
\(\displaystyle \sum_{i\in S}a_i(D/b_i)\ge c(D/d).\)
The bit length of \(D\) is \(O(L)\), because the sum of the encoded denominator lengths is at most \(L\). Every scaled mass and threshold lies between \(0\) and \(D\), and the selected masses sum to at most \(1\). Hence the calculation uses integers of \(O(L)\) bits. Schoolbook multiplication and division give an \(O(L^3)\) arithmetic bound.
The certificate length is \(O(\tau H\log(m+1))\). A conservative verification-time bound is
\(\displaystyle O\!\left(\tau H(m+L)^2+L^3\right).\)
Since \(p\) is fixed and \(m,\tau\le L\), these bounds are polynomial in the input length.
We reduce from \(\mathrm{3SAT}\). Let \(F\) have variables \(a_1,\ldots,a_n\) and clauses \(B_1,\ldots,B_s\).
Introduce clause variables \(c_1,\ldots,c_s\) and two gate variables \(f,g\). The net has \(m_0=n+s+2\) variables and exactly the following rules:
\(\neg f\land\neg g:a_j>\neg a_j\).
\(\top:f>\neg f\).
\(f\land\neg g\land\lambda:c_k>\neg c_k\).
\(f\land c_1\land\cdots\land c_s:g>\neg g\).
\(g:\neg v>v\).
Here \(\top\) denotes the empty conjunction. Every condition excludes its effect variable, as required. The rule list has polynomial encoded size.
Let \(x\) set every variable to \(0\). Let \(y\) set \(f=g=1\) and every assignment and clause variable to \(0\).
Suppose \(F\) has a satisfying assignment. While \(f=g=0\), set precisely its true assignment variables to \(1\). Set \(f=1\). For each clause, a true literal enables a rule setting its clause variable to \(1\). Once every \(c_k=1\), set \(g=1\). Finally, use the cleanup rules to reset every assignment and clause variable to \(0\). This reaches \(y\), so \(y\succ_C x\).
Conversely, suppose an improving sequence reaches \(y\) from \(x\). Both \(f\) and \(g\) can change only from \(0\) to \(1\). The flip setting \(g=1\) requires \(f=1\) and every \(c_k=1\).
Between the flip setting \(f=1\) and the flip setting \(g=1\), assignment variables cannot change: their upward rules require \(f=0\), and their downward rules require \(g=1\). They therefore represent one fixed assignment throughout this interval.
Every clause variable starts at \(0\), and its upward rules require \(f=1\). For \(c_k\) to be \(1\) when \(g\) is set, a literal of \(B_k\) must have been true under that fixed assignment. Consequently every clause is satisfied, and \(F\) is satisfiable.
Thus \(F\) is satisfiable if and only if \(y\succ_C x\).
Consider any improving sequence, starting at an arbitrary outcome.
Every improving sequence therefore has length at most \(2(n+s)+2=2m_0-2\). In particular, \(\operatorname{diam}(C)\le 2m_0-2\). This bound holds globally, independently of whether \(F\) is satisfiable.
Because \(p\) is nonconstant and positive on all positive integers, its leading coefficient is positive. There are constants \(b>0\) and \(t_0\), depending only on \(p\), such that \(p(t)\ge bt\) for every integer \(t\ge t_0\).
Choose
\(\displaystyle m=\max\!\left\{m_0,t_0,\left\lceil 2m_0/b\right\rceil\right\}.\)
Add \(m-m_0\) variables appearing in no rule, and set them to \(0\) in both endpoints. These variables never change. The enlarged preference graph consists of disjoint copies of the original graph, so its diameter is unchanged, and dominance between the chosen endpoints is unchanged.
Now \(\operatorname{diam}(C)\le 2m_0-2\le p(m)\). Also \(m=O(m_0)\), with constants depending only on the fixed \(p\), so the padding is polynomial.
Finally, use the singleton society \(\tau=1\), \(\mu_1=1\), with \(q=1\). Then
\(\displaystyle M_\mu(y,x)\ge1\quad\Longleftrightarrow\quad y\succ_C x\quad\Longleftrightarrow\quad F\text{ is satisfiable}.\)
The reduction always produces promised inputs. Together with Section 3, it proves \(\mathrm{NP}\)-completeness for every fixed nonconstant \(p\).
For each type, enumerate all variable-index sequences of lengths \(1,\ldots,H\), simulate their flips, and test whether any valid sequence reaches \(y\). Section 2 proves this decides dominance, including when \(x=y\).
There are at most \(\sum_{j=1}^{H}m^j\le(m+1)^H\) candidates per type. After determining all dominance indicators, sum their masses exactly. A conservative deterministic bound is
\(\displaystyle O\!\left(\tau H(m+1)^H(m+L)^2+L^3\right),\qquad H=p(m)+1.\)
For the constant polynomial \(p(m)=K\), this becomes
\(\displaystyle O\!\left(\tau(m+1)^{K+1}(m+L)^2+L^3\right),\)
where the hidden constant may depend on \(K\). This is polynomial in \(L\).
Hence the classification is complete: constant diameter bounds give polynomial-time solvability; every fixed nonconstant polynomial diameter bound gives \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly resolves the promised threshold problem: every fixed nonconstant positive integer-valued polynomial bound gives \(\mathrm{NP}\)-completeness, whereas every fixed constant bound gives a polynomial-time algorithm. No major or minor mathematical issues were found.
The distinction between constant and nonconstant polynomials is necessary under the literal wording of USER_TASK. The proof establishes hardness for every fixed nonconstant bound rather than assuming the cited theorem supplies this stronger quantifier.
The output uses the required explicit rule representation and imposes no local completeness or consistency condition. Its algorithms operate on promised inputs without checking the diameter promise.
The attribution to Theorem 5 is correct: the cited paper states \(\mathrm{NP}\)-completeness of dominance with polynomially bounded diameter. [Kronegger, Lackner, Pfandler and Pichler, Theorem 5](https://martin.lackner.xyz/publications/kr-minimal.pdf).
The output supplies its own reduction for the claim covering every fixed nonconstant polynomial, so that claim does not depend on an unstated interpretation of the cited theorem.
For distinct endpoints, a true dominance assertion makes the ordered pair reachable. Its shortest directed-path distance is therefore bounded by \(p(m)\).
For identical endpoints, the output correctly distinguishes positive-length dominance from the zero distance assigned to identical vertices. The first flip of a closed improving walk reaches an outcome \(z\ne x\). The remaining walk establishes reachability from \(z\) to \(x\), so the promise bounds a shortest return path by \(p(m)\). Including the first flip yields a positive-length witness of length at most \(p(m)+1\).
Thus the claimed common witness bound \(H=p(m)+1\) is valid even in cyclic nets.
The certificate construction is sound:
Completeness also holds: all dominating types can be included, and Section 2 bounds every required witness. For \(q=0\), the empty subset correctly certifies acceptance.
The certificate length \(O(\tau H\log(m+1))\) is polynomial because \(p\) is fixed and the explicit outcomes and support imply \(m,\tau\le L\). Conflicting rules do not invalidate the verifier: applicability of any sanctioning rule suffices under the task’s semantics.
With positive denominators, \(D=d\prod_i b_i\) is divisible by every denominator used. Multiplying the threshold comparison by \(D\) therefore gives exactly the stated integer inequality.
The encoded denominator lengths bound the bit length of \(D\) by \(O(L)\). Since the masses are positive and sum to one, each scaled mass and every selected partial sum lie between zero and \(D\). The same bound holds for the scaled threshold because \(q\in[0,1]\).
The conservative \(O(L^3)\) schoolbook arithmetic bound is valid. Likewise,
\[ O\!\left(\tau H(m+L)^2+L^3\right) \]
is a valid conservative bound for certificate verification. No numerical approximation enters the decision.
Every constructed rule has a conjunction of literals excluding its effect variable. The long conjunction in the rule for \(g\) is permitted by USER_TASK, and its explicit encoding has polynomial size.
The forward implication is valid. A satisfying assignment can be selected before setting \(f\); each satisfied clause then permits its clause variable to be set; all clause variables permit \(g\); and the cleanup rules reach the specified endpoint.
The reverse implication is also valid:
This establishes satisfaction of every clause. The cleanup phase cannot undermine this reasoning because its rules require \(g=1\), after the clause-certification requirement has already been met.
The diameter argument applies to arbitrary initial outcomes, not merely to the reduction’s chosen endpoints.
Each gate changes at most once. Every assignment or clause variable can increase only with \(g=0\) and decrease only with \(g=1\). Since \(g\) never decreases, each such variable changes at most twice. Therefore every improving sequence has length at most
\[ 2(n+s)+2=2m_0-2. \]
This bounds every reachable pair’s shortest distance. Unreachable pairs and identical endpoints have distance zero by definition, so they cause no exception.
For a nonconstant polynomial positive on all positive integers, the leading coefficient is positive, and the stated eventual lower bound \(p(t)\ge bt\) is valid. The chosen padding size satisfies both \(m\ge t_0\) and \(bm\ge2m_0\), giving
\[ \operatorname{diam}(C)\le2m_0-2\le p(m). \]
Variables appearing in no rules cannot flip. Their fixed values partition the enlarged graph into copies of the original graph, preserving diameter and the selected dominance question. The padding is linear in \(m_0\), with constants depending only on fixed \(p\).
The singleton society then gives exactly the stated equivalence with satisfiability. Both yes- and no-instances produced by the reduction satisfy the promise.
Enumerating positive-length variable-index sequences through length \(H\) decides dominance by the verified witness bound, including identical endpoints.
The candidate count
\[ \sum_{j=1}^{H}m^j\le(m+1)^H \]
holds for every \(m\ge1\), including \(m=1\). Simulating these candidates and performing the exact mass comparison gives the claimed conservative running time.
For fixed \(p(m)=K\), the exponent \(K+1\) is constant. The resulting running time is polynomial in \(L\), as claimed.
None. The write-up establishes its classification and running-time claims under the stated promise.
The final continuous_status records the established hardness for nonconstant bounds. The constant-bound exception is also proved; this is dependence on the chosen diameter bound, not an encoding-dependent split.
⟨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.