On Circuit-Size Complexity and the Low Hierarchy in NP
Ker‐I Ko, Uwe Schöning · SIAM Journal on Computing · 1985
Let A be a set having polynomial size circuits. If A is also known to be in NP, then we may conclude that the graph of the polynomial size circuits for A is actually in $\Pi _2^p $. Using this observation, we show that sets in NP which have polynomial size ciruits are in $L_3^p $, the third level of the low hierarchy in NP. By a similar technique, we are able to show that some other intuitively low sets in NP are in $L_2^p $, and even in a certain refinement of $L_2^p $. As a consequence, sparse sets are not strong nondeterministic polynomial time Turing complete in NP unless the polynomial time hierarchy collapses to $\Delta _2^p $.