= Undecidable unary languages with linear-size circuits
{title2=$U_A=\{1^n:n\in A\}$}
For any set of lengths $A$, choose at length $n$ a constant-zero <Boolean circuit> when $n\notin A$, and an AND of all inputs when $n\in A$. This uses $O(n+1)$ gates. If $A$ is <undecidable>, so is $U_A$, yet it belongs to <P poly>. Since all <NP> languages are decidable by certificate enumeration, this proves <P poly> is not equal to <NP>; it does not resolve containment in the other direction.
Back to article page
