Was ist die minimal erforderliche Reduktionstiefe für die NP-Härte von SAT?

14

Wie jeder weiß, ist SAT vollständig für in Polynom-Zeit-Viel-Eins-Reduktionen. Es ist immer noch vollständig, wenn viele Reduzierungen vorgenommen wurden.A C 0NPEINC0

Meine Frage ist, welche Mindesttiefe für die Reduzierungen erforderlich ist. Formeller,

Was ist die am wenigsten , so dass SAT -hard WRT many-one Reduzierungen?N P A C 0 ddNPEINCd0

Es scheint mir, dass ausreichen sollte? Kennt jemand eine Referenz?EINC20

cc.complexity-theory reference-request np-hardness circuit-complexity reductions Kaveh
quelle
3
Auf den ersten Blick scheint es so, als ob Ihre Frage von "Manindra Agrawal, Eric Allender, Steven Rudich, Reduzierung der Schaltungskomplexität: Ein Isomorphism Theorem und ein Gap Theorem, JCSS 57: 127-143, 1999" beantwortet werden sollte. Sie sagen: "Wir beweisen, dass alle Sätze, die für NP unter AC0-Reduzierungen abgeschlossen sind, unter Reduzierungen abgeschlossen sind, die über die Tiefe von zwei AC0-Schaltungen berechenbar sind." Aber mir fehlt vielleicht etwas.
Robin Kothari
@Robin, danke, ich werde die Reduzierung der Schaltungskomplexität prüfen : Ein Isomorphismussatz und ein Lückensatz .
Kaveh
@Robin, ich denke, es beantwortet meine Frage positiv: " Theorem 10. (Gap Theorem) Sei C eine geeignete Komplexitätsklasse. Die Mengen, die für C unter ungleichmäßigen AC0-Reduktionen schwer sind, sind für C unter ungleichmäßigen NC0-Reduktionen schwer. " und „ Corollary 4. für jede richtige Komplexitätsklasse C, jeder Satz komplett für C unter NC0 Reduzierungen abgeschlossen unter Reduzierungen Tiefen zwei AC0 Schaltungen und umkehrbar durch Tiefe drei AC0 Schaltungen berechenbar. “ , wo geeignete Mittel " geschlossen unter DLogTime-Uniform NC1 Reduzierungen ". Möchten Sie es als Antwort posten, damit ich es akzeptieren kann?
Kaveh
Ok, ich werde es umbuchen.
Robin Kothari

Antworten:

8

Umbuchen meines Kommentars:

Auf den ersten Blick scheint es so, als ob Ihre Frage von "Manindra Agrawal, Eric Allender, Steven Rudich, Reduzierung der Schaltungskomplexität: Ein Isomorphism Theorem und ein Gap Theorem , JCSS 57: 127-143, 1999" beantwortet werden sollte . Sie sagen: "Wir beweisen, dass alle Sätze, die für NP unter AC0-Reduzierungen abgeschlossen sind, unter Reduzierungen abgeschlossen sind, die über die Tiefe von zwei AC0-Schaltungen berechenbar sind." Aber mir fehlt vielleicht etwas.

Robin Kothari
quelle