Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Learning Reductions to Sparse Sets
verfasst von : Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
Erschienen in: Mathematical Foundations of Computer Science 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.