= Solution
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> is
$$
\boxed{\mathrm{P/poly}=\bigcup_{d\geq0}\mathrm{SIZE}(O(n^d))}.
$$
There 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 (complexity)> encodings and running the polynomial-time verifier. If $U_A$ were decidable, testing $1^n$ would decide $A$, a contradiction. Therefore
$$
\boxed{U_A\in\mathrm{P/poly}\setminus\mathrm{NP},\qquad\mathrm{P/poly}\ne\mathrm{NP}}.
$$
This separates the classes in the stated direction; it does not claim that <NP> is not contained in <P poly>.
Back to article page
