Answer: Polynomial-time solvable: the continuous valid-value decision problem belongs to \(\mathrm{P}\).
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe k-wCVD-SAT problem with variable k, is strongly NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution \(\mu\) over complete configuration-request types, each with an MDD of feasible whole-configuration paths and additive costs \(c_{j,t}\), current type-level settings, and cohort-average limits \(K_j\), determine for a target type \(t_0\), variable \(x_i\), and value \(a\) whether there are path flows for each type such that all mass of \(t_0\) uses paths with \(x_i=a\) and \(\sum_t \mu_t \mathbb{E}[c_{j,t}] \le K_j\) for every cost \(j\). The values passing this feasibility test form the valid domain.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types.
There are \(m\ge1\) variables \(x_1,\ldots,x_m\) with explicitly listed nonempty finite domains \(D_i\). Each type supplies an explicit ordered MDD \(M_t=(V_t,E_t)\), a current partial assignment \(\rho_t\), and unary cost tables \(c_{j,t,i}:D_i\to\mathbb Q\) for \(j=1,\ldots,k\), where \(k\ge1\) is part of the input. Costs and bounds \(K_j\in\mathbb Q\) are binary encoded and may have either sign.
Each MDD has a root, one accepting terminal, and value-labeled edges with distinct labels at each node; every accepting path assigns every variable exactly once in the stated order, with no skipped layers. Its paths represent feasible whole configurations. Let \(P_t\) contain the accepting paths agreeing with \(\rho_t\), and put \(c_{j,t}(p)=\sum_{i=1}^{m}c_{j,t,i}(p_i)\).
A mass allocation for type \(t\) is a distribution \(q_t\) over \(P_t\), with nonnegative real path weights summing to \(1\); mass may split among whole paths. Given a supported target type \(t_0\), a variable \(x_i\) unassigned in \(\rho_{t_0}\), and \(a\in D_i\), call \(a\) valid if such allocations exist with \(q_{t_0}(\{p:p_i=a\})=1\) and \(\sum_t\mu_t\sum_{p\in P_t}q_t(p)c_{j,t}(p)\le K_j\) for every \(j\). The valid domain consists of all values passing this test.
Let \(S=\sum_t(|V_t|+|E_t|)\), \(d=\sum_i|D_i|\), and \(L\) be the total binary input length; state running times in \(m,\tau,k,S,d,L\).
Is this continuous valid-value decision problem solvable in polynomial time in \(m,\tau,k,S,d,L\), or is it NP-hard?
For a single whole configuration, feasibility under an input number \(k\) of additive cost bounds is strongly NP-hard, even for an MDD representing every assignment and nonnegative integer costs with equal positive bounds. [Andersen, Hadzic, and Pisinger](https://arxiv.org/pdf/1401.3830)
No result settling this exact distribution-over-types feasibility problem was identified in the literature search.
The continuous valid-value decision problem is solvable in polynomial time, even when \(k\) is part of the input and costs and bounds have either sign.
The key is an exact representation of distributions over accepting paths by nonnegative flows on the explicit MDDs.
Fix the queried type \(t_0\), variable \(x_i\), and value \(a\).
For every type \(t\), delete edges inconsistent with \(\rho_t\). For \(t_0\), additionally delete edges assigning \(x_i\) a value other than \(a\). Then retain only vertices and edges lying on a root-to-accepting-terminal path. Denote the resulting graph by \(G_t=(V'_t,E'_t)\), with root \(r_t\) and accepting terminal \(z_t\).
Its accepting paths are exactly
\(P'_t=P_t\) for \(t\ne t_0\), and \(P'_{t_0}=\{p\in P_{t_0}:p_i=a\}\).
If any \(P'_t\) is empty, the answer is immediately negative: that supported type cannot receive a distribution of total weight \(1\). Emptiness is checked by graph reachability.
Henceforth assume every \(G_t\) has an accepting path. Each graph is acyclic, and every accepting path assigns every variable exactly once.
For an edge \(e\in E'_t\), let \(h_t(e)\) be the variable index assigned by that edge and let \(v_t(e)\) be its value label. Define its cost by
\(w_{j,t,e}=c_{j,t,h_t(e)}(v_t(e))\).
For every accepting path \(p\),
\(\displaystyle \sum_{e\in p}w_{j,t,e}=c_{j,t}(p)\).
This identity uses the hypothesis that paths assign every variable exactly once without skipped layers.
Introduce a variable \(f_{t,e}\) for every retained edge. It represents the amount of society mass of type \(t\) traversing that edge.
Write \(\delta_t^+(v)\) and \(\delta_t^-(v)\) for the outgoing and incoming edges of \(v\). Define \(b_{t,r_t}=\mu_t\), \(b_{t,z_t}=-\mu_t\), and \(b_{t,v}=0\) at all other vertices.
Consider the following linear feasibility system:
\(\displaystyle f_{t,e}\ge 0\qquad(t,\ e\in E'_t),\)
\(\displaystyle \sum_{e\in\delta_t^+(v)}f_{t,e}-\sum_{e\in\delta_t^-(v)}f_{t,e}=b_{t,v}\qquad(t,\ v\in V'_t),\)
\(\displaystyle \sum_t\sum_{e\in E'_t}w_{j,t,e}f_{t,e}\le K_j\qquad(j=1,\ldots,k).\)
We prove that this system is feasible if and only if the queried value is valid.
Suppose allocations witnessing validity exist. For every retained edge, set
\(\displaystyle f_{t,e}=\mu_t\sum_{\substack{p\in P'_t\\e\in p}}q_t(p).\)
These quantities are nonnegative. Each path contributes its weight once to the outgoing flow at the root, once to the incoming flow at the terminal, and equally to incoming and outgoing flow at every internal vertex. Since the path weights sum to \(1\), all flow equations hold.
For each cost index \(j\), exchanging finite sums gives
\(\displaystyle \sum_t\sum_{e\in E'_t}w_{j,t,e}f_{t,e}=\sum_t\mu_t\sum_{p\in P'_t}q_t(p)\sum_{e\in p}w_{j,t,e}=\sum_t\mu_t\sum_{p\in P'_t}q_t(p)c_{j,t}(p).\)
The last expression is at most \(K_j\) by the assumed allocation feasibility. Thus the linear system is feasible.
Suppose the linear system is feasible. Fix a type \(t\).
We prove directly that its edge flow decomposes into accepting paths. Initially its residual source mass is \(\mu_t\). Whenever the residual source mass is positive, the root has a positive-flow outgoing edge. Follow such an edge.
At any internal vertex reached along a positive-flow edge, flow conservation implies that some outgoing edge also has positive flow. The graph is finite and acyclic, so this process must terminate. It can terminate only at \(z_t\): an internal vertex with positive incoming flow cannot have zero outgoing flow. We have therefore found a positive-flow accepting path \(p\).
Let \(\lambda\) be the minimum residual edge flow on \(p\). Subtract \(\lambda\) from every edge of \(p\). This operation:
No zero edge becomes positive later. Consequently, at most \(|E'_t|\) such operations are possible. The procedure cannot end with positive residual source mass, because that would yield another positive-flow accepting path.
Once the residual source mass is zero, all residual vertex balances are zero. A nonnegative balanced flow on a DAG is zero: in a topological ordering, the first vertex has zero incoming flow and hence zero outgoing flow; induction gives the same conclusion at every subsequent vertex.
Thus the original flow has a decomposition
\(\displaystyle f_{t,e}=\sum_{\ell:e\in p_{t,\ell}}\lambda_{t,\ell},\qquad \lambda_{t,\ell}>0,\qquad \sum_\ell\lambda_{t,\ell}=\mu_t.\)
Because \(\mu_t>0\), define
\(\displaystyle q_t(p)=\frac{1}{\mu_t}\sum_{\ell:p_{t,\ell}=p}\lambda_{t,\ell}.\)
This is a distribution over \(P'_t\). In particular, every path receiving positive weight for \(t_0\) assigns \(x_i=a\), so the target-value condition holds.
Applying the same finite-sum identity as above shows that the allocations’ aggregate expected costs equal the linear program’s cost expressions. All bounds therefore hold. This proves the equivalence.
Neither direction requires costs or bounds to be nonnegative.
Let \(N=\sum_t|E'_t|\) and \(H=\sum_t|V'_t|\). Then \(N+H\le S\).
The system has:
Replacing each equality by two inequalities gives at most \(2H+N+k\le 2S+k\) inequalities.
Every numerical coefficient is an input cost, an input mass, an input bound, or one of \(0,1,-1\). Using mass flows avoids multiplying masses by costs. Hence every coefficient has binary length at most \(L+O(1)\). A dense encoding of the entire system has length
\(\displaystyle B=O\bigl((S+k+1)(S+1)(L+1)\bigr).\)
Constructing the restricted graphs and this encoding takes polynomially many bit operations in \(m,\tau,k,S,d,L\).
The standard polynomial-time linear programming theorem decides exact feasibility of rational linear systems, including systems with equalities and lower-dimensional feasible sets, in time polynomial in their binary encoding length. Rational coefficients can also be cleared row by row with only polynomial growth in encoding length before applying the integer-data theorem. See [MIT’s lecture on polynomial-time linear programming feasibility](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/60dd52896e183e2c60bfe40e076d83d3_MIT15_083JF09_lec10.pdf).
Therefore a single valid-value query takes
\(\displaystyle (m+\tau+k+S+d+L+2)^{O(1)}\)
bit operations. Testing every value in the queried variable’s domain computes its complete valid domain in
\(\displaystyle |D_i|\,(m+\tau+k+S+d+L+2)^{O(1)}\le d\,(m+\tau+k+S+d+L+2)^{O(1)}.\)
These are polynomial bounds in the binary input length, rather than bounds depending polynomially on numerical magnitudes.
The cited hardness theorem concerns selecting one path satisfying every bound. Its reduction does not establish hardness when bounds apply to expected costs under a path distribution. [Andersen, Hadzic, and Pisinger, Theorem 7](https://arxiv.org/pdf/1401.3830).
For a concrete distinction, take one type of mass \(1\), two binary variables, and an MDD representing every assignment. Query \(x_1=0\). Give \(x_1\) zero costs, and define the two cost tables for \(x_2\) by
\(\displaystyle (c_{1,1,2}(0),c_{2,1,2}(0))=(0,2),\qquad (c_{1,1,2}(1),c_{2,1,2}(1))=(2,0).\)
Set \(K_1=K_2=1\). No whole configuration satisfies both bounds. Nevertheless, placing weight \(1/2\) on each of \((0,0)\) and \((0,1)\) gives expected cost vector \((1,1)\), and the queried value is valid.
The flow formulation captures these mixtures exactly, while preserving feasibility of every whole path used. Thus the stated continuous problem belongs to \(\mathrm{P}\); NP-hardness under polynomial-time reductions would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The flow formulation is exact, has polynomial encoding size, and supports exact feasibility testing in polynomial time. I found no major or minor mathematical issues.
The retained graphs inherit the ordered MDD structure and acyclicity. Since \(m\ge1\), a retained accepting path has positive length, so its root and accepting terminal are distinct. There are no retained edges entering the root or leaving the terminal. These structural facts justify the source and terminal equations used subsequently.
The variables represent society mass, rather than conditional probabilities. Consequently, the source supply for type \(t\) is correctly set to \(\mu_t\), and the aggregate cost constraints correctly use coefficients \(w_{j,t,e}\) without another mass factor.
All path sets are finite, so exchanging the sums is valid. The resulting cost expression is exactly the aggregate expected cost appearing in the task. For the target type, probability one on the queried value means paths excluded by the additional restriction have zero weight. Thus the construction applies to every allocation witnessing validity.
Positive residual source supply guarantees a positive outgoing edge. At each reached internal vertex, conservation guarantees a positive outgoing edge. Finiteness and acyclicity prevent indefinite continuation, and conservation prevents termination at an internal vertex.
The minimum edge flow on the selected path is positive and cannot exceed the residual source supply. Subtraction therefore preserves nonnegativity and correctly updates the source and terminal balances. Each subtraction permanently eliminates at least one positive edge, establishing the claimed bound of \(|E'_t|\) operations.
The argument that a nonnegative balanced flow on a DAG is zero is explicitly supplied and correct. Consequently, the decomposition accounts for every original edge flow, and the extracted weights sum to \(\mu_t\). Dividing by the strictly positive input mass yields a normalized distribution. Its support enforces the queried value, and the same finite-sum identity preserves every cost bound.
\[
2H+N+k\le 2S+k.
\]
All numerical entries are copied from the input or are fixed constants. Negative masses in terminal right-hand sides require only a sign bit. The stated dense encoding bound is therefore a valid polynomial upper bound.
The invoked theorem concerns exact feasibility of explicitly encoded rational linear inequalities in polynomial bit complexity. Equalities can be replaced by paired inequalities, and clearing denominators by positive row multipliers preserves feasibility with polynomial encoding growth. The cited [MIT lecture](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/60dd52896e183e2c60bfe40e076d83d3_MIT15_083JF09_lec10.pdf) states polynomial solvability for integer-data feasibility and addresses arbitrary polyhedra and finite precision. Its hypotheses are satisfied after the stated transformations; lower-dimensional feasible sets pose no missing condition.
Both the single-query runtime and the additional factor \(|D_i|\le d\) for the complete queried domain meet the requested polynomial bounds.
The example is correct: the two available cost vectors are \((0,2)\) and \((2,0)\), neither satisfies both bounds \(1\), while their equal mixture has expected vector \((1,1)\). Both configurations satisfy the queried value. The final statement about NP-hardness implying \(\mathrm{P}=\mathrm{NP}\) follows correctly from the polynomial algorithm.
No additional clarification or repair is needed.
⟨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.