d4-journals-jair-2011-0040

NEW RESULT — discrete: hard → continuous: hard · adversarial review: proved

Answer: $\mathrm{NP}$-complete, hence $\mathrm{NP}$-hard; in $\mathrm P$ if and only if $\mathrm P=\mathrm{NP}$.

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

Given a variable set $\mathbf V$, state cardinalities $r$, a finite support $\mathcal T$ of DAG types with positive rational masses $\mu_G$ summing to $1$, and a positive integer $d$, does there exist a DAG $H$ over $\mathbf V$ such that $I(H)\subseteq\bigcap_{G\in\mathcal T}I(G)$ and $\kappa_r(H)\le d$, where $\kappa_r(H)=\sum_{B\in\mathbf V}\left(\prod_{A\in Pa_H(B)}r_A\right)(r_B-1)$?

Packaged proof task (what the prover saw — nothing else)

Let $\mathbf V$ be a nonempty variable set with $m=|\mathbf V|$, and let each state cardinality $r_A\ge 2$ be an integer given in binary.
A society is given by its support: a list $\mathcal T$ of $\tau$ distinct DAG types on $\mathbf V$, each with positive binary rational mass $\mu_G$, with $\sum_{G\in\mathcal T}\mu_G=1$. Here $\tau$ is the support size, not the number of possible DAG types.
Let $I(G)$ denote all conditional independence statements given by d-separation in $G$, and let $Pa_H(B)$ denote the parents of $B$ in $H$.
Define $\kappa_r(H)=\sum_{B\in\mathbf V}\bigl(\prod_{A\in Pa_H(B)}r_A\bigr)(r_B-1)$, with empty product $1$.
Given a positive binary integer $d$, decide whether there exists a DAG $H$ on $\mathbf V$ satisfying $I(H)\subseteq\bigcap_{G\in\mathcal T}I(G)$ and $\kappa_r(H)\le d$.
Let $L$ be the total binary input length; state running times in $m,\tau,L$.

Is this decision problem in $\mathrm P$, or is it $\mathrm{NP}$-hard?

For an explicitly listed finite collection of DAGs, the corresponding decision problem is NP-complete; hardness already holds for three DAGs with prescribed state cardinalities. [Peña](https://arxiv.org/pdf/1101.1715)
No separate complexity result explicitly formulated for the positive rational mass version was identified in the literature search.

Modeling choices made when packaging the task

Prover output (gpt-6.1-sol / high, Bolzano prover prompt)

Result

The problem is $\mathrm{NP}$-complete. Positive rational masses do not change the decision problem because feasibility depends only on the explicitly listed support. Consequently, it belongs to $\mathrm P$ if and only if $\mathrm P=\mathrm{NP}$.

1. Polynomial reduction establishing hardness

Use the explicit-list problem stated in the question: given DAGs $G_1,\ldots,G_t$, state cardinalities $r_A$, and a threshold $d$, decide whether some DAG $H$ satisfies

$$ I(H)\subseteq\bigcap_{i=1}^{t}I(G_i), \qquad \kappa_r(H)\le d. $$

This problem is $\mathrm{NP}$-hard even for three DAGs with prescribed state cardinalities. The parameter formula and independence constraint in Peña’s construction are exactly those used here. [Peña, Section 3, Theorem 2](https://arxiv.org/pdf/1101.1715)

Remove duplicate DAGs from the source list, obtaining the distinct DAGs $F_1,\ldots,F_s$. Construct the target instance by keeping $\mathbf V$, all $r_A$, and $d$, and setting

$$ \mathcal T=\{F_1,\ldots,F_s\}, \qquad \mu_{F_j}=\frac1s. $$

These masses are positive binary rationals and sum to $1$. Each requires $O(\log(s+1))$ bits. Moreover, removing duplicate factors from an intersection changes nothing, so

$$ \bigcap_{j=1}^{s}I(F_j) = \bigcap_{i=1}^{t}I(G_i). $$

Thus, for every candidate $H$, both its independence constraint and its parameter count are unchanged. The source instance is a yes-instance if and only if the constructed target instance is a yes-instance.

For source input length $\ell$, a straightforward implementation using adjacency matrices, pairwise duplicate comparisons, and binary arithmetic takes

$$ O\!\left( \ell+t^2m^2\log(m+1)+t\log^2(t+1) \right) $$

bit operations. The added mass descriptions occupy $O(t\log(t+1))$ bits. Hence this is a polynomial-time many-one reduction. Applied to the three-DAG hard instances, it establishes hardness with support size at most three and equal masses.

2. Polynomial verification of the independence constraint

A certificate is the adjacency matrix of a candidate $H$, requiring $O(m^2)$ bits. Check acyclicity and find a topological order $\alpha$.

For $B\in\mathbf V$, let $\operatorname{Pre}_\alpha(B)$ be its predecessors in that order, and define the ordered local statement

$$ B\perp \operatorname{Pre}_\alpha(B)\setminus Pa_H(B) \mid Pa_H(B). $$

The standard ordered-local-basis theorem states that, for a DAG and a consistent ordering, its d-separation model is the graphoid closure of these statements. DAG d-separation models are graphoids: they satisfy symmetry, decomposition, weak union, contraction, and intersection. These are precisely the facts used in Peña’s polynomial verification argument. [Peña, Theorem 3](https://arxiv.org/pdf/1101.1715)

Their hypotheses hold here: $H$ is a DAG, $\alpha$ is consistent with it, and each support graph $G$ is a DAG. Therefore,

$$ I(H)\subseteq\bigcap_{G\in\mathcal T}I(G) $$

holds if and only if every ordered local statement above holds by d-separation in every $G\in\mathcal T$.

Indeed, necessity follows because each local statement belongs to $I(H)$. For sufficiency, each $I(G)$ contains the local statements and is closed under the graphoid rules, so it contains their closure, namely $I(H)$.

There are $m\tau$ tests. A standard d-separation algorithm takes $O(m+|E(G)|)$ graph operations per test, giving the bound

$$ O\!\left( m\sum_{G\in\mathcal T}(m+|E(G)|) \right) = O(\tau m^3). $$

In particular, there is no need to enumerate all conditional independence statements.

3. Binary arithmetic and total running time

Let $b_A$ denote the binary length of $r_A$, and put

$$ B_r=\sum_{A\in\mathbf V}b_A\le L. $$

For each summand of $\kappa_r(H)$, the parents and the child are distinct variables. Since $r_A<2^{b_A}$,

$$ \left(\prod_{A\in Pa_H(B)}r_A\right)(r_B-1) < 2^{B_r}. $$

Consequently,

$$ \kappa_r(H)<m\,2^{B_r}, $$

so its binary length is at most $B_r+\lceil\log_2m\rceil+1=O(L)$. Thus binary cardinalities cause no exponential arithmetic cost.

There are $O(m^2)$ multiplications. Using schoolbook multiplication, exact computation and comparison with $d$ take $O(m^2L^2)$ bit operations.

For the valid inputs specified in the question, a conservative total verifier bound is therefore

$$ O\!\left( L+\tau m^3\log(m+1)+m^2L^2 \right). $$

The certificate length and verification time are polynomial in $L$, proving membership in $\mathrm{NP}$. Combined with the reduction, this proves $\mathrm{NP}$-completeness.

For completeness, enumerating all loop-free directed adjacency matrices gives a deterministic decision algorithm with running time

$$ O\!\left( 2^{m(m-1)} \left[L+\tau m^3\log(m+1)+m^2L^2\right] \right). $$

All occurrences of $\tau$ here refer to the listed support size.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6.1-sol / medium, Bolzano verifier prompt)

Verdict

The prover resolves the task correctly: the decision problem is $\mathrm{NP}$-complete. The reduction preserves feasibility, the independence constraint has a polynomial verifier, and binary state cardinalities do not invalidate the arithmetic bounds. No major or minor mathematical issues were found.

Step-by-step verification

1. Use of the cited hardness result

The source problem has the same independence inclusion and parameter-count constraint as the target problem. Peña’s parameter formula agrees with $\kappa_r$, and Theorem 2 establishes hardness using three DAGs with prescribed state cardinalities. The construction uses cardinalities satisfying the target requirement $r_A\ge 2$. Thus the cited hard instances fall within the permitted input domain. [Peña, Section 3](https://arxiv.org/pdf/1101.1715)

The prover uses this result as a cited theorem; it does not need to reproduce its underlying hardness proof.

2. Reduction to distinct support graphs with rational masses

Removing duplicate DAGs preserves the intersection of their independence models. It also leaves every candidate’s parameter count unchanged, since the variable set and all state cardinalities remain unchanged.

The source hard instances have a nonempty graph list, so the number $s$ of distinct graphs is positive. Consequently, every assigned mass $1/s$ is positive, and their sum is exactly one.

Under the standard encoding of a binary rational as a binary numerator and denominator, each such mass requires $O(\log(s+1))$ bits. This is consistent with the task’s rational input model; terminating binary expansions are not required.

The reduction therefore preserves both yes-instances and no-instances. Duplicate removal can reduce three listed DAGs to fewer distinct graphs, so the prover correctly claims hardness for support size at most three.

The stated reduction time conservatively covers reading the source, constructing adjacency matrices, comparing graph pairs, and writing the rational masses. Its output size and running time are polynomial in the source input length.

3. Certificate and independence verification

An adjacency matrix specifies a candidate graph using $O(m^2)$ bits. Acyclicity can be checked and a topological order obtained in polynomial time.

For a topological order $\alpha$, every parent of $B$ precedes $B$. Hence the three sets in the ordered local statement are disjoint, as required for conditional independence notation.

The invoked theorem is stated sufficiently precisely: the graphoid closure of the ordered local statements equals the DAG’s d-separation model. Peña’s Theorem 3 explicitly uses this equality to establish polynomial verification. Its hypotheses apply here because $H$ and every support graph are DAGs and $\alpha$ is consistent with $H$. [Peña, Theorem 3](https://arxiv.org/pdf/1101.1715)

Both implications are justified:

Necessity follows because each ordered local statement belongs to $I(H)$.
Sufficiency follows because each $I(G)$ contains those statements and is closed under the stated graphoid rules.

An empty set of predecessor nonparents yields a vacuous statement and creates no exceptional case.

There are $m\tau$ tests. The linear graph-operation bound per d-separation test gives
\[ O\!\left(m\sum_{G\in\mathcal T}(m+|E(G)|)\right)=O(\tau m^3). \]
The additional logarithmic factor in the final bit-operation bound is conservative.

4. Binary arithmetic

The bit-length calculation is valid. A DAG has no self-loop, so the child and its parents are distinct variables. Thus each summand satisfies
\[ \left(\prod_{A\in Pa_H(B)}r_A\right)(r_B-1)<2^{B_r}. \]
Summing over the $m$ variables gives $\kappa_r(H)<m2^{B_r}$.

Since $B_r\le L$ and the input explicitly supplies the variables’ cardinalities, the resulting integer has $O(L)$ bits. Intermediate products obey the same bound. The claimed $O(m^2L^2)$ arithmetic cost therefore safely covers multiplication, summation, and comparison with $d$.

5. Complexity conclusion and edge cases

The certificate length and stated verifier time
\[ O\!\left(L+\tau m^3\log(m+1)+m^2L^2\right) \]
are polynomial in the explicit input length. Membership in $\mathrm{NP}$, together with the reduction, establishes $\mathrm{NP}$-completeness.

The single-variable case, empty parent sets, and support size one cause no failure. The deterministic enumeration bound also correctly counts all loop-free directed adjacency matrices; cyclic candidates can be rejected during verification.

The verifier is expressly stated for valid inputs, matching the task’s input restrictions. Positive masses impose no additional feasibility condition beyond specifying the support.

No repair or additional mathematical clarification is needed.