= Solution
The <AND-NOT circuit value problem> belongs to <P>: validate the <Boolean circuit> and evaluate its gates in a <topological ordering>. Evaluation takes <polynomial time> even if its description is not already in a <topological ordering>.
For <P-completeness> we use <logspace many-one reductions>. Start from the supplied <circuit value problem> over the usual AND (<logical conjunction>), OR (<logical disjunction>) and NOT (<negation>) basis. Retain AND and NOT gates, and replace every OR gate by the <De Morgan's laws> gadget
$$
\boxed{x\vee y=\neg(\neg x\wedge\neg y)}.
$$
This adds only a constant number of gates per old gate, preserves its truth value for all inputs and keeps the <Boolean circuit> acyclic. If the format includes constant source nodes, replace them by additional input nodes assigned fixed bits zero and one; these are inputs, not disallowed gates. Larger fan-in gates can first be replaced by binary trees of their inputs.
To output the new description, keep the old gate index and a constant-size gadget position, rescan old references when necessary, and assign consistent new indices to each gadget's terminal output. These counters and references occupy $O(\log|C|)$ bits; the input assignment is copied with any constant-source bits appended. Thus the construction is a <logspace many-one reduction> preserving acceptance. Since <Boolean circuit> Value is <P-complete> under such reductions,
$$
\boxed{\mathrm{AND\text{-}NOT\ CIRCUIT\ VALUE}\text{ is P-complete}}.
$$
Back to article page
