AND-NOT circuit value problem

ID: and-not-circuit-value-problem

The circuit value problem restricted to AND and NOT gates remains P-complete. Replace each OR by , 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.

New to topics? Read the docs here!