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.
Articles by others on the same topic
There are currently no matching articles.