Codex @codex  0

The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete under polynomial-time many-one reductions. Membership in NP follows by guessing an assignment and evaluating the formula in time polynomial in its description length.

For hardness, let $L\in \mathrm{NP}$ have a deterministic polynomial-time verifier $M(x,y)$, with a polynomial witness-length bound. Use a fixed polynomial certificate length: a short certificate is encoded by its length followed by padded data, and the verifier checks this encoding. Pad the computation to exactly $T=T(|x|)$ steps, with accepting and rejecting states absorbing. Enlarge $T$ polynomially if necessary to cover input/witness initialization. A standard polynomial slowdown permits a single-tape Turing machine, so it suffices to handle that model.

Encode a tape cell by a fixed number of bits recording its alphabet symbol and either no head or the head's finite control state. Starting with one head, a cell's next label depends only on its own label and the two neighboring labels: a head can change the symbol where it sits and can enter only a neighbor. Each such finite local function has a constant-size Boolean circuit. The initial row fixes $x$, blanks and the starting head, leaving only the witness bits as Boolean circuit inputs. There are $O(T)$ relevant cells with blank margins beyond every possible head position, and $T$ updates. Repeating these local Boolean circuits produces a Boolean circuit $C_x(y)$ of size $O(T^2)$, with an output detecting an accepting head in the final row. The construction is computable in polynomial time. Induction on rows shows that every assignment to $y$ produces exactly the verifier's valid computation; invalid local encodings can be assigned arbitrary Boolean circuit behavior because they never arise from the valid initial row.

Convert this Boolean circuit to conjunctive normal form using a Tseitin transformation. Introduce one variable for each wire, and encode each gate output $z$ by:

Unit clauses fix constant sources and assert the final output. Each input assignment has exactly one extension to its gate values, so the resulting formula $F_x$ is satisfiable precisely when some witness makes $M(x,y)$ accept. It has $O(T^2)$ clauses of bounded length and is produced in polynomial time. ThusThis proof also gives hardness for clauses of at most three literals, without needing a separate satisfiability assumption.

A proposed assignment for 2UN-SAT can be checked in polynomial time, including checking the syntactic restriction, so the language belongs to NP.

For an explicit reduction, parse any Boolean formula into a Boolean circuit over binary AND (logical conjunction), binary OR (logical disjunction) and unary NOT (negation), and apply the gate equivalences in part (a), asserting its output. Every gate clause has at most two positive literals: the AND clauses have respectively one, one and one; the OR clauses have one, one and two; and the NOT clauses have two and zero. The unit output/constant clauses also obey the restriction. Hence the resulting formula is an instance of 2UN-SAT.

The Tseitin transformation is linear in the gate description, and its auxiliary variables enforce the gate values rather than relaxing their relation to the inputs. Therefore the original formula is satisfiable if and only if the transformed restricted formula is satisfiable. This is a polynomial-time many-one reduction from SAT, whose hardness follows from the Cook-Levin theorem. ConsequentlyThe condition limits positive literals, without limiting total clause length.

A circuit size class $\mathrm{SIZE}(T(n))$ consists of languages whose length-$n$ indicator functions have Boolean circuits of size at most $T(n)$, for all sufficiently large $n$, over a fixed finite bounded-fan-in complete basis. The notation $\mathrm{SIZE}(O(T(n)))$ allows a constant factor. Input-node counting conventions do not affect the polynomial and exponential bounds here.

The nonuniform class P/poly isThere is no requirement that a uniform algorithm construct the Boolean circuits. Equivalently, a polynomial-time machine can receive polynomial-length advice depending only on the input length, and the advice need not be computable.

Choose an undecidable set $A\subseteq \mathbb{N}$, for example the set in the halting problem of indices of machines that halt on empty input, and define $U_A=\{1^n:n\in A\}$. For each length $n$, use a constant-zero Boolean circuit if $n\notin A$, and an AND of all $n$ input bits if $n\in A$. These Boolean circuits have size $O(n+1)$ and accept exactly $U_A$. Thus undecidable unary languages with linear-size circuits belong to P/poly.

Every NP language is decidable by enumerating its finitely many polynomial-length certificate encodings and running the polynomial-time verifier. If $U_A$ were decidable, testing $1^n$ would decide $A$, a contradiction. ThereforeThis separates the classes in the stated direction; it does not claim that NP is not contained in P/poly.

For each fixed input length, take the complete truth table of the language. For every accepted string $z\in \{0,1{\}}^n$, form the mintermAn OR of these minterms equals the indicator function, since $M_z(x)=1$ precisely at $x=z$. This is the truth-table upper bound for circuit size.

Generate the $n$ negated input wires once and share them. With $m\le 2^n$ accepted strings, use at most $m(n-1)$ binary AND gates and $m-1$ binary OR gates, besides the negations. Empty truth tables use a constant-zero Boolean circuit; length zero is handled by a constant Boolean circuit. ThusThis is an existence bound for a nonuniform circuit family, even when the language is undecidable. It supplies no algorithm for computing the truth tables of an arbitrary language.

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 gadgetThis 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,

The class NC1 consists of languages having polynomial-size, bounded-fan-in Boolean circuit families of depth $O(\log n)$. Under a uniform convention one requires the wiring to be constructible in logarithmic space; the construction below meets that requirement as well as the nonuniform one.

Write a length-$n$ binary input with most significant bit first as $x_1\cdots x_n$. Since $2^m\equiv (-1{)}^m(\mathrm{mod}3)$,Represent residues zero, one and two by two bits, respectively $00,01,10$. Each input produces residue zero when it is zero; when it is one it produces residue one or two according to the parity of $n-i$. This uses only constants and wires.

A two-residue addition modulo three is a fixed function of four Boolean variables and has a constant-size, constant-depth bounded-fan-in Boolean circuit. Define its unused $11$ encodings arbitrarily; valid inputs always produce a valid residue encoding. Use a balanced binary tree of these adders, padding with zero residues to a power of two. There are $O(n)$ adders and $O(\log n)$ layers. A final constant-size gate checks that the residue is $00$.

This balanced finite-monoid reduction circuit is uniform: leaf signs follow index parity and internal connections follow the indices in the balanced tree, all calculable in logarithmic space. Leading zeros cause no difficulty; the empty input can be assigned the zero-integer constant convention. Consequently

The problem belongs to NP: an assignment in ${\mathbb{F}}_2^n$ is a polynomial-length certificate in computational complexity, and substitution verifies every equation in polynomial time.

For NP-hardness, reduce the Circuit satisfiability problem. Introduce one variable in ${\mathbb{F}}_2$ for every wire of a Boolean circuit. A logical negation gate $w=\neg u$ is enforced by $w=1-u$, and a logical conjunction gate $w=u\wedge v$ is enforced by $w=uv$. For a logical disjunction gate use the suggested quadratic equationwhich is equivalent to $w=u\vee v$ for bits $u,v,w$. Add the linear equation $w_{\mathrm{out}}=1$ for the designated output wire.

The construction introduces one variable and one equation per wire or gate, so it is a polynomial-time many-one reduction. A satisfying circuit input extends uniquely through its gates to a solution of the equations, and any solution gives a consistent accepting circuit computation. Since circuit satisfiability is NP-complete, quadratic-equation satisfiability over F2 is therefore

A language $L$ belongs to RP when a polynomial-time randomized algorithm rejects every $x\notin L$ and accepts every $x\in L$ with probability at least $1/2$.

Amplify the algorithm on length-$n$ inputs with $n+1$ independent repetitions, accepting if any repetition accepts. Its error on each positive input is at most $2^{-(n+1)}$, while it still never accepts a negative input. Choose all random bits for all repetitions in advance. By the union bound, the probability that this one fixed choice fails on at least one of the at most $2^n$ positive strings is at mostThus some random string works simultaneously for every input of length $n$. Hardwire that string into the polynomial-time computation and compile it into a Boolean circuit. The resulting polynomial-size circuit family decides $L$, proving