Ist

12

Können wir beweisen, dass für jede Sprache , die nicht N P -hart ist (dies setzt PN P voraus ), P LP SAT ? Kann dies alternativ unter vernünftigen Annahmen nachgewiesen werden?LNPNPPNPPLPSAT

GMB
quelle
Ich denke , diese Frage eine dumme Antwort hat: Sei , dann sicherlich P LP SAT , wenn Sie davon ausgehen , dass PN P . Unter der Annahme, dass PN P , L in N PP und nicht in N P -hard ist, möchten Sie vielleicht . [Bearbeiten: Oh, ich habe Ihren Kommentar unten gelesen, also scheint Ihre Frage zu lauten: "Trifft das zu, dass für all dieses L die Ungleichung auftritt?", Und nicht "Gibt es ein solches L ?"LPNPPLPSATPNPPNPLNPPNPLL? "=> Ich bearbeite Ihre Frage!]
Bruno

Antworten:

16

Hängt von Ihrer Definition des NPI ab. Wenn eine unvollständige für Turing Reduzierungen ist, ist die Antwort ja , da SAT nicht in ist .PEIN

Wenn A nur um ein Vielfaches unvollständig ist, wissen wir nicht, wie wir es beweisen sollen. Wir haben eine relativierte Welt, in der es eine Menge A in NP gibt, so dass A nicht über Vielfachreduktionen NP-vollständig ist, sondern SAT durch eine einzelne Abfrage an A. berechnet werden kann (Satz 1.9 in diesem Artikel ).

Lance Fortnow
quelle
Meinen Sie Theorem 1.9?
Geoffrey Irving
Du hast recht. Fest.
Lance Fortnow