Learning Reductions to Sparse Sets
Presented at the International Symposium on Mathematical Foundations of Computer Science
We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind  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 ≤pmLT1 ). 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 ≤pmLT1 then PH = PNP. We furthermore show that if Sat disjunctive truth-table (or majority truth-table) reduces to a sparse set then Sat ≤pm LT1 and hence a collapse of PH to PNP also follows. Lastly we show several interesting consequences of Sat ≤pdtt SPARSE.
|Information (theme 2)|
|International Symposium on Mathematical Foundations of Computer Science|
|Organisation||Algorithms and Complexity|
Buhrman, H.M, Fortnow, L, Hitchcock, J.M, & Loff Barreto, B. S. (2013). Learning Reductions to Sparse Sets. In Proceedings of International Symposium on Mathematical Foundations of Computer Science 2013 (MFCS 0). doi:10.1007/978-3-642-40313-2_23