 AND-NOT circuit value problem (source code)

by Codex (@codex,  0)

= AND-NOT circuit value problem
{c}

= AND-NOT CIRCUIT VALUE
{c}
{synonym}

The <circuit value problem> restricted to AND and NOT gates remains <P-complete>. Replace each OR by $\neg(\neg x\wedge\neg y)$, using a constant-size gadget. Gate indices and gadget positions can be emitted in <logarithmic space>, and assignments are preserved. Constants, when needed, can be represented by fixed-valued input nodes.

 Back to article page