We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind~\cite{AA:96} 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 \leq_m^p \LT$). They claim that as a consequence $\PTIME = \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 \leq_m^p \LT$ then $\PH = \PTIME^\NP$. We furthermore show that if $\SAT$ disjunctive truth-table (or majority truth-table) reduces to a sparse set then $\SAT \leq_m^p \LT$ and hence a collapse of $\PH$ to $\PTIME^\NP$ also follows. Lastly we show several interesting consequences of $\SAT \leq_{dtt}^p \SPARSE$.

CWI Deliverables
Algorithms and Complexity

Buhrman, H., Fortnow, L., Hitchcock, J., & Loff Barreto, B. S. (2012). Learning Weak Reductions to Sparse Sets. CWI Deliverables. CWI.