CircuitSAT is NP-complete

A verifier first rejects a malformed list. Otherwise it guesses one bit for every input gate, evaluates the gates in topological order, and accepts iff the designated output is $1$. Its time is polynomial in the list length, so $\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}\mathrm{S}\mathrm{A}\mathrm{T}\in \mathrm{N}\mathrm{P}$.

Given a Boolean formula $\phi$, create one circuit input for each variable and one circuit gate for each connective, ordered from leaves toward the root; designate the root gate as output. This map is polynomial time and produces a circuit $C_{\phi }$ satisfying $C_{\phi }(a)=\phi (a)$ for every assignment $a$. Therefore $\phi \in \mathrm{S}\mathrm{A}\mathrm{T}$ iff $C_{\phi }\in \mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}\mathrm{S}\mathrm{A}\mathrm{T}$, so [L2] and [L3] give NP-hardness.

Combining membership from step 1.1 with hardness from step 1.2 proves NP-completeness by [L4].