Learning Reductions to Sparse Sets

Abstract We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind [1] 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 \mathrm{LT}_1\) ). They claim that P= NP follows as a consequence, 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 \mathrm{LT}_1\) then PH = P 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 1 and hence a collapse of PH to P NP also follows. Lastly we show several interesting consequences of Sat \(\leq_{dtt}^p\) SPARSE.

Authors

• Harry Buhrman
• Lance Fortnow
• John M. Hitchcock
• Bruno Loff

Keywords

No keywords are indexed for this paper.