Abstract: We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind (1996) who study the consequences of SAT being many-one reducible to functions computable by non-uniform circuits consisting of a single weighted threshold gate (SAT many-one reduces to LT₁). They claim that as a consequence P = NP follows, but unfortunately their proof was incorrect.

We take up this question and use results from computational learning theory to show that if SAT many-one reduces to LT₁ then PH = P^NP.

We furthermore show that if SAT disjunctive truth-table (or majority truth-table) reduces to a sparse set then SAT many-one reduces to LT₁ and hence a collapse of PH to P^NP also follows. Lastly we show several interesting consequences if SAT disunctive truth-table reduces to a sparse set.

• Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (Klosterneuberg, Austria, August 26-30, 2013). Lecture Notes in Computer Science 8087, pages 243-253, Springer-Verlag, 2013.
  [DOI | PDF]