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!