Answer: \(\mathsf{coNP}\)-complete under polynomial-time many-one reductions, and \(\mathsf{NP}\)-hard under polynomial-time Turing reductions, even with maximum in-degree \(2\). It is in \(\mathsf{P}\) if and only if \(\mathsf{P}=\mathsf{NP}\).
Theorem 10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\fi \allconv\ is co-\NP-hard even if $G$ is a DAG with maximum in-degree of $3$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite Boolean SyDS template \(S=(G,\{f_v\})\), where \(G\) is a DAG of maximum in-degree \(3\), consider an atomless unit-mass population of independent copies of \(S\). Each copy has an internal configuration \(q\in\{0,1\}^{V(G)}\) and follows the template's synchronous update. Decide whether every measurable initial population profile reaches, after some finite time, a profile in which almost every copy is at a fixed point.
Input is a Boolean synchronous dynamical system \(S=(G,\{f_v\})\), where \(G\) is a finite simple DAG with maximum in-degree \(3\), \(m=|V(G)|\), and each deterministic function \(f_v:\{0,1\}^{\delta^-(v)\cup\{v\}}\to\{0,1\}\) is given by its truth table; \(\delta^-(v)\) denotes the in-neighbors of \(v\). Define \(F(q)_v=f_v(q|_{\delta^-(v)\cup\{v\}})\), with all vertices updated simultaneously. Self-state dependence is allowed and does not count toward in-degree.
The population is \([0,1]\) with Lebesgue measure \(\lambda\). An initial profile is any measurable map \(Q_0:[0,1]\to\{0,1\}^{V(G)}\); copies evolve independently by \(Q_t(a)=F^t(Q_0(a))\).
A finitely encoded society is given by its support: the list of its \(\tau\) positive-mass configuration types, each with its mass as a binary rational, summing to \(1\). Here \(\tau\) is support size, not \(2^m\). Let \(L\) be the total input bit length; express running times in \(m,\tau,L\), noting that only \(S\) is input and societies are universally quantified. The measurable-profile quantifier also includes profiles with irrational type masses.
Decide whether \(\forall Q_0\ \exists T\in\mathbb{Z}_{\geq0}:\lambda(\{a:F(Q_T(a))=Q_T(a)\})=1\). The finite time \(T\) may depend on the profile, and different copies may reach different fixed points.
Is this universal population-convergence decision problem in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard under polynomial-time Turing reductions?
Discrete convergence guarantee is \(\mathsf{coNP}\)-hard even for Boolean DAG systems of maximum in-degree \(3\). [Source](https://arxiv.org/pdf/2312.08385)
For DAG systems, discrete convergence guarantee is \(\mathsf{coNP}\)-complete. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/17351/17158)
No publication explicitly treating this atomless population formulation was located.
The universal population-convergence problem is \(\mathsf{coNP}\)-complete under polynomial-time many-one reductions, and therefore \(\mathsf{NP}\)-hard under polynomial-time Turing reductions. This holds even when the maximum in-degree is \(2\).
Consequently, the problem belongs to \(\mathsf{P}\) if and only if \(\mathsf{P}=\mathsf{NP}\).
The proof below establishes the population equivalence, a polynomial-time verifier for nonconvergence, and a direct bounded-degree hardness reduction.
Write \(\Omega=\{0,1\}^{V(G)}\). Say that a configuration \(q\in\Omega\) converges if there exists \(t\geq 0\) such that \(F^{t+1}(q)=F^t(q)\). Once this equality holds, every subsequent configuration is the same fixed point.
For a measurable profile \(Q_0\), define
\[
\]
\(E_q=Q_0^{-1}(\{q\})\), \(\qquad p_q=\lambda(E_q)\), \(\qquad q\in\Omega.\)
The sets \(E_q\) form a finite measurable partition, so \(p_q\geq 0\) and \(\sum_{q\in\Omega}p_q=1\). Determinism and independent evolution give, for every \(t\geq 0\),
\[
\]
\(\lambda(\{a:F(Q_t(a))=Q_t(a)\})=\sum_{\{q:F^{t+1}(q)=F^t(q)\}}p_q.\)
Thus a particular profile satisfies the requested convergence property exactly when every configuration with positive mass converges:
It follows that
\[
\]
\(\text{universal population convergence}\quad\Longleftrightarrow\quad\text{every }q\in\Omega\text{ converges}.\)
For the forward implication, apply the population property to each constant measurable profile \(Q_0(a)=q\). The reverse implication follows from the finite-support argument above.
This argument allows arbitrary real masses, including irrational masses. Although the population is atomless, the configuration space is finite. Moreover, every failure already has a witness society with support size \(\tau=1\) and rational mass \(1\).
This stronger time bound uses both Boolean states and acyclicity.
For each vertex \(v\), define its height recursively by
\[
\]
\(h(v)=1+\max_{u\in\delta^-(v)}h(u),\)
where the maximum over an empty set is \(0\). Because \(G\) is a DAG, these heights are well defined. If \(m>0\), their maximum \(H\) satisfies \(H\leq m\).
Lemma. If an orbit \(q_t=F^t(q_0)\) eventually reaches a fixed point, then the coordinate \(q_t(v)\) is constant for all \(t\geq h(v)\).
Proof. Proceed in topological order. Assume the claim holds for every in-neighbor of \(v\), and put
\[
\]
\(p=\max_{u\in\delta^-(v)}h(u)=h(v)-1.\)
All in-neighbor coordinates are constant from time \(p\) onward. Denote their constant tuple by \(b\). Hence, for every \(t\geq p\), the coordinate at \(v\) follows the autonomous unary Boolean map
\[
\]
\(q_{t+1}(v)=g(q_t(v)),\qquad g(s)=f_v(b,s).\)
There are exactly four unary Boolean maps: the two constant maps, the identity, and negation.
Negation cannot occur here, because it would make \(q_t(v)\) alternate forever, contradicting the assumed eventual fixed point. For the identity, the coordinate is already constant from time \(p\). For either constant map, it is constant from time \(p+1=h(v)\).
This also covers sources, for which \(p=0\), and completes the induction. \(\square\)
Therefore every convergent orbit is fixed by time \(H\), and in particular by time \(m\). Equivalently, for every initial configuration \(q\),
\[
\]
\(q\text{ converges}\quad\Longleftrightarrow\quad F^{m+1}(q)=F^m(q).\)
When \(m=0\), the unique empty configuration is already fixed, so the same equivalence holds.
Together with Section 1, this also shows that every yes-instance admits the common population convergence time \(T=m\), independently of the profile.
A certificate that universal population convergence fails is an initial configuration \(q\), encoded by \(m\) bits.
The verifier computes \(F^m(q)\) and checks whether \(F^{m+1}(q)\neq F^m(q)\). By Section 2, this inequality holds exactly when \(q\) does not converge. Section 1 then makes the constant profile at \(q\) a population counterexample.
Each local truth table has at most \(2^4=16\) entries: at most three in-neighbor bits and one self-state bit. After parsing the input, one synchronous update uses \(O(m)\) table evaluations. Verification therefore uses \(O(m^2)\) table evaluations and polynomial time in the input length \(L\). Thus the problem belongs to \(\mathsf{coNP}\).
For clarity, the following bounds count word operations after storing the constant-size truth tables:
| Task | Running time |
|---|---|
| Test convergence from one supplied configuration | \(O(L+m^2)\) |
| Test convergence of a supplied valid society with support size \(\tau\) | \(O(L+\tau m^2)\) |
| Decide universal convergence by enumerating all configurations | \(O(L+2^m m^2)\) |
These bounds give polynomial bit-time algorithms for the first two tasks.
For the supplied-society task, simulate each of its \(\tau\) positive-mass types and apply Section 1. The promised positive masses need no arithmetic: their magnitudes do not affect the answer. Here \(L\) includes the supplied society encoding.
For the actual universal decision problem, only \(S\) is input, so \(L\) is the encoding length of \(S\), and \(\tau\) is not an input parameter. The exponential enumeration bound does not replace \(2^m\) by the support size of a particular society.
We give a polynomial-time many-one reduction from \(\mathsf{UNSAT}\) for formulas in \(3\)-CNF, using the standard \(\mathsf{coNP}\)-completeness of that problem.
Let \(\varphi\) be such a formula. Construct an acyclic Boolean circuit computing \(\varphi\), with gates of fan-in at most \(2\):
All gate vertices are distinct, and every gate takes inputs only from preceding vertices. Hence the resulting graph is a finite simple DAG of maximum in-degree \(2\). The circuit has size polynomial in the formula length. A formula with no clauses can instead use a constant-\(1\) output.
Turn this circuit into a synchronous dynamical system as follows. Each variable vertex preserves its initial bit:
\[
\]
\(f_{x_i}(s)=s.\)
Each circuit gate computes its usual Boolean operation on its in-neighbor states and ignores its own state.
Let \(o\) be the circuit output. Add one final vertex \(z\), with the sole incoming edge \(o\to z\), and define
\[
\]
\(f_z(b,s)=b(1-s),\)
where \(b\) is the state of \(o\) and \(s\) is the self-state of \(z\). Thus \(z\) becomes \(0\) when the output is \(0\), and toggles when the output is \(1\).
The new vertex is a sink, so the graph remains a simple DAG of maximum in-degree \(2\). Every local function has a constant-size truth table, making the construction polynomial-time.
Consider any initial configuration, including arbitrary initial values at all gates and at \(z\). The variable vertices preserve an assignment \(a\).
Give input vertices circuit depth \(0\), and each gate depth one plus the maximum depth of its inputs. Induction on depth shows that a gate of depth \(d\) has its correct circuit-evaluation value at every time \(t\geq d\): its update reads predecessor values from time \(t-1\), when those predecessors are already correct.
Let \(D\) be the maximum circuit depth. At every time \(t\geq D\), all circuit vertices are stable and the output equals \(\varphi(a)\).
If \(\varphi\) is unsatisfiable, this output is \(0\). Consequently \(z\) is \(0\) from time \(D+1\) onward. The entire configuration is then fixed.
Since the initial configuration was arbitrary, every configuration converges.
Suppose an assignment \(a\) satisfies \(\varphi\). Initialize each variable according to \(a\), and initialize each gate to its correct circuit-evaluation value.
The entire circuit is fixed from time \(0\), and \(o\) remains \(1\). Consequently,
\[
\]
\(q_{t+1}(z)=1-q_t(z)\qquad\text{for every }t\geq 0.\)
Thus \(z\) alternates forever, and the configuration never reaches a fixed point. Its constant population profile witnesses failure of universal population convergence.
We have proved
\[
\]
\(\varphi\in\mathsf{UNSAT}\quad\Longleftrightarrow\quad S_\varphi\text{ has universal population convergence}.\)
This establishes \(\mathsf{coNP}\)-hardness under polynomial-time many-one reductions. Together with Section 3, it establishes \(\mathsf{coNP}\)-completeness.
Given a \(3\)-CNF formula \(\varphi\), construct \(S_\varphi\), ask one universal-convergence oracle query, and negate the oracle’s answer. By Section 4, the resulting answer decides satisfiability.
Therefore the problem is \(\mathsf{NP}\)-hard under polynomial-time Turing reductions. This conclusion does not assert \(\mathsf{NP}\)-hardness under many-one reductions.
The discrete classification agrees with Theorem 5.1 of [Rosenkrantz et al., *Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms*](https://cdn.aaai.org/ojs/17351/17351-13-20845-1-2-20210518.pdf). The direct proof above independently verifies the truth-table encoding and the bounded in-degree restriction needed here.
Finally, if the population problem were in \(\mathsf{P}\), the one-query reduction would put \(3\)-SAT in \(\mathsf{P}\), implying \(\mathsf{P}=\mathsf{NP}\). Conversely, that equality implies \(\mathsf{coNP}=\mathsf{P}\), and Section 3 would then put the population problem in \(\mathsf{P}\).
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested hardness classification. The population equivalence, convergence-time bound, certificate verifier, and bounded-degree reduction are mathematically sound. I found no major issue.
The appropriate status is proved_with_minor_gaps: the exceptional constant-output circuit needs a depth convention, and the displayed-equation formatting contains empty displays. Neither affects the substantive result.
Verified.
Because the configuration space \(\Omega\) is finite and \(Q_0\) is measurable, its fibers \(E_q\) form a finite measurable partition. Consequently, the masses \(p_q\) are nonnegative and sum to one.
The displayed measure identity is correct: every individual initially in \(E_q\) occupies \(F^t(q)\) at time \(t\), so the fixed-point test is constant throughout that fiber.
Both directions of the profile-specific equivalence are justified:
There is no hidden restriction to rational masses. Zero-mass fibers do not affect the conclusion, even if they contain individuals with nonconvergent trajectories.
For universal convergence, constant measurable profiles correctly establish the forward implication. The reverse implication follows from the finite partition argument. Different types may reach different fixed points; the proof never assumes a common fixed point.
The claim that every failure has a rational witness society of support size \(\tau=1\) is also correct.
Verified.
The height recursion is well defined on a finite DAG. With source height one, the maximum height is at most \(m\) whenever \(m>0\).
The induction is conditional on the entire orbit eventually reaching a fixed point. This hypothesis correctly applies to each predecessor coordinate. At time
\(p=h(v)-1\), all predecessor coordinates are already constant, so the update at \(v\) becomes an autonomous unary Boolean map.
The classification into two constant maps, identity, and negation is exhaustive. Negation is excluded by the eventual-fixed-point hypothesis. Identity gives constancy immediately from time \(p\), while a constant map gives constancy from time \(p+1\). The synchronous-update indices are correct.
The source case is explicitly covered. Once every coordinate is constant from its height onward, the entire configuration is fixed at time \(H\), hence at time \(m\).
Thus the equivalence
\[
q\text{ converges}\quad\Longleftrightarrow\quad F^{m+1}(q)=F^m(q)
\]
is correct. The empty-vertex case is separately and correctly addressed.
The resulting common population time \(T=m\) for yes-instances follows.
Verified.
A certificate consists of \(m\) initial-state bits. The verifier’s inequality characterizes nonconvergence exactly by Section 2, rather than merely detecting failure to converge within an arbitrary cutoff.
Each local table has at most sixteen entries, including self-state dependence. Computing \(m+1\) synchronous updates therefore requires \(O(m^2)\) table evaluations for \(m>0\), with the empty system handled directly.
The runtime table explicitly uses word operations. It does not assert that these same bounds hold unchanged in every bit-cost model; its weaker assertion of polynomial bit time for the first two tasks is justified.
For a promised valid society, testing all positive-mass types is sufficient. No mass arithmetic is needed to decide convergence. The discussion correctly distinguishes the augmented input length for a supplied society from the actual universal problem, whose input consists only of \(S\).
The enumeration bound correctly retains \(2^m\); universal quantification cannot be replaced by the support of one supplied society.
Verified, with one minor edge-case omission.
The stated use of coNP-completeness of \(3\)-CNF unsatisfiability is appropriate.
Distinct literal-occurrence gates prevent repeated literals from requiring parallel graph edges. Binary clause and conjunction gates give maximum in-degree two. Identity updates at variable vertices use only the permitted self-state dependence.
The circuit is acyclic, and adding the sink \(z\) preserves acyclicity and simplicity. Every constructed truth table has constant size, so the construction is polynomial in the formula encoding length.
For an unsatisfiable formula, arbitrary initial gate states are correctly allowed. The depth induction establishes eventual correct gate values using predecessor states from the preceding time step. Once the output is permanently zero, the update at \(z\) makes it permanently zero one step later.
For a satisfiable formula, initializing all gates to their evaluated values makes the circuit fixed immediately. The final vertex then alternates forever. This supplies a valid nonconvergent configuration and constant-profile witness.
The reduction direction is correct: unsatisfiability corresponds to universal convergence.
Minor issue: the no-clause case introduces a constant-output gate, but the later gate-depth definition takes a maximum over its inputs without specifying the empty-input convention. The minimum clarification is to specify the depth and stabilization convention for this constant gate. This affects only the stated exceptional case and requires no new mathematical argument.
Verified.
The direct reduction and membership argument establish coNP-completeness under polynomial-time many-one reductions, including the stronger in-degree-two restriction.
A satisfiability algorithm using one convergence-oracle query and complementing its answer is a valid polynomial-time Turing reduction. Combined with NP-completeness of \(3\)-SAT, this establishes the requested NP-hardness under polynomial-time Turing reductions.
Both directions of the claimed equivalence with \(\mathsf{P}=\mathsf{NP}\) follow correctly.
The cited [Theorem 5.1](https://cdn.aaai.org/ojs/17351/17351-13-20845-1-2-20210518.pdf) does state coNP-completeness of DAG convergence guarantee, with additional restrictions to three levels and \(3\)-symmetric functions. It corroborates the discrete classification. The prover does not rely on it to establish the bounded-in-degree or truth-table claims, so no unverified theorem application remains.
Minor issue: numerous equations are preceded by empty display-math environments. Remove these empty environments and place each intended equation in a single valid math environment. The formulas remain readable as written, so this is a presentation defect only.
⟨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.