Näherungshärte unter Annahme von NP! = CoNP

32

Zwei der häufigsten Annahmen zum Nachweis der Härte von Approximationsergebnissen sind und Unique Games Conjecture. Gibt es eine Härte der Näherungsergebnisse unter der Annahme von ? Ich suche nach Problem so dass "es schwierig ist, innerhalb eines Faktors sei denn, ".N P c o N P A A α N P = c o N PPNPNPcONPEINEINαNP=cONP

Es ist bekannt, dass "das Zeigen des Faktors NP-Härte für das kürzeste Vektorproblem implizieren würde, dass ". Beachten Sie, dass dies das "Gegenteil" von dem ist, wonach ich suche.N P = c o N PnNP=cONP

Klarstellung: Es ist möglich, dass und die Frage P gegen NP noch offen ist. Ich suche nach der Härte des Approximationsergebnisses, die falsch wird, wenn aber von nicht beeinflusst wird (dh immer noch als Vermutung bleibt) .N P = c o N P P N PNP=cONPNP=cONPPNP

Shiva Kintali
quelle
@ Kintali, Das SVP-Ergebnis ist interessant. Kennen Sie andere Beispiele, die dem kürzesten Vektorproblem ähneln?
Mohammad Al-Turkistany
Mir sind keine derartigen Ergebnisse mehr bekannt.
Shiva Kintali

Antworten:

20

Hier ist eine einfache Beobachtung. Wenn Sie von , ist es ziemlich einfach zu erkennen, dass es N P- Optimierungsprobleme gibt , die in gewissem Sinne nicht einmal über gute nicht deterministische Approximationsalgorithmen verfügen .NPcONPNP

Zum Beispiel besagt das PCP-Theorem, dass Sie SAT in das Problem der Unterscheidung übersetzen können, ob der Klauseln erfüllt sind und alle Klauseln erfüllt sind, für einige ε > 0 . Angenommen , es ein nichtdeterministischen Algorithmus ist , die zwischen diesen beiden Fällen in dem Sinne , dass der nichtdeterministischen Algorithmus in jedem Berechnungspfad berichten kann entweder „zufrieden“ oder „höchstens unterscheiden können 1 - ε “, und er sagt , „höchstens 1 - ε "in einem Pfad, wenn höchstens 1 - ε1-εε>01ε1-ε1-εkann erfüllt werden, andernfalls wird in jedem Berechnungspfad "alle erfüllt" angegeben, wenn alle Gleichungen erfüllt werden können. Das ist genug , um SAT in entscheiden , , so N P = c o N P . Es scheint klar , dass die Existenz eines solchen nichtdeterminismus keinen Einfluss darauf , ob hat P = N P .cONPNP=cONPP=NP

Es ist durchaus plausibel , dass ein „natürliches“ Szenario existiert: ein Optimierungsproblem , das in annähernd schwer zu deterministisch polynomialer Zeit unter , aber nicht unter seine hart bekannt P N P . (Dies ist wahrscheinlich das, was Sie wirklich fragen wollten.) Viele Härten von Approximationsergebnissen werden zuerst unter einer stärkeren Annahme bewiesen (z. B. N P nicht in subexponentieller Zeit oder N P nicht in B P P ). In einigen Fällen schwächen spätere Verbesserungen die notwendige Annahme, manchmal bis auf P NNPcONPPNPNPNPBPP . Es besteht also die Hoffnung, dass Ihre Frage etwas zufriedenstellender beantwortet wird als diese. Es ist schwerzu fragenwie es könnte ein Problem seindasnicht kannschwer nachweisbar in determinis polytime unter angenähert P N P , aber eskannschwer unter bewiesen werden N P c o N P . Das würde bedeuten, dass N P c o N P etwas über deterministische Berechnungen aussagt, das P N P nicht bereits sagt; intuitiv ist dies schwer zu begreifen.PNPPNPNPcONPNPcONPPNP

Ryan Williams
quelle
Ja. Es ist schwer zu begreifen, dass solche Härteergebnisse überhaupt möglich sind. Ich habe mich gefragt, ob wir das Fehlen solcher Härteergebnisse nachweisen können. Puh ... es wird kompliziert.
Shiva Kintali 20.10.10
(1) Ich fürchte, Sie schreiben den Ja-Fall und den Nein-Fall im zweiten Absatz gegensätzlich. Es ist einfach, einen nicht deterministischen Algorithmus zu konstruieren, der das tut, was Sie angegeben haben (meldet "alle erfüllt" in mindestens einem Pfad, wenn die Formel erfüllbar ist, und meldet "höchstens 1 - ε" in allen Pfaden, wenn die Formel bei weitem nicht erfüllbar ist ) indem einfach alle Wahrheitszuweisungen nicht deterministisch getestet werden. (2) Ich stimme dem schwer fassbaren Teil zu.
Tsuyoshi Ito
8

Haftungsausschluss: Dies ist keine direkte Antwort.

Tatsächlich gibt es viel mehr Härtebedingungen als P! = NP und UGC. David Johnson schrieb bereits 2006 eine schöne Kolumne für die Transactions on Algorithms zu genau diesem Thema. Er listet die zahlreichen verschiedenen Annahmen auf, die verwendet werden, um die Härte zu zeigen, und wie sie miteinander zusammenhängen.

Leider sind dies alles NP gegen deterministische Klassen (mit Ausnahme von NP und Co-AM). NP vs co-NP wird überhaupt nicht abgedeckt.

Suresh Venkat
quelle
2
Interessanterweise spricht David Johnson in der nächsten Spalte über NP vs co-NP - NP-Vollständigkeit Spalte Nummer 26 !
Daniel Apon
ach natürlich. Ich hätte mich erinnern sollen. Aber keine Annäherungen ...
Suresh Venkat
4

ist eine stärkere Hypothese als P N P, da N P c o N P P N P impliziert. Jede Härte des Näherungsergebnisses unter der Annahme von P N P würde sich also auch aus derAnnahmevon N P c o N P ergeben .NPcONPPNPNPcONPPNPPNPNPcONP

Mohammad Al-Turkistany
quelle
3
Es ist möglich, dass NP = coNP und die Frage P vs NP noch offen ist. Ich suche nach einer Annäherungshärte, die falsch wird, wenn NP = coNP, aber von P! = NP nicht beeinflusst wird (dh immer noch als Vermutung bleibt).
Shiva Kintali
In Ihrer Frage suchen Sie nach Problem A, das besagt, dass "es einfach ist, innerhalb eines Faktors zu approximieren α impliziert NP = coNP", was äquivalent ist zu "Wenn N P c o N P, dann ist es schwierig, A innerhalb eines Faktors zu approximieren α ". Bitte bearbeiten Sie Ihre Frage, um Ihren Kommentar wiederzugeben. EINαNPcONPα
Mohammad Al-Turkistany
0

Dies ist keine direkte Antwort

k-Auswahlproblem ist -vollständig. Unter der Annahme, dass N P c o N P ist , ist die k-Auswahl strikt schwieriger als die k-Färbung in allgemeinen Graphen. Daher ist die Annäherung der chromatischen Listenzahl strikt schwieriger als die chromatische Zahl. Es ist bekannt, dass die k-Färbung für zweigeteilte Graphen trivial ist. Die Bestimmung der listenchromatischen Anzahl von zweigeteilten Graphen ist jedoch N P -hart. (auch 3-Wahlmöglichkeit ist P 2 -vollständig)2PNPcONPNP2P

Noga Alon, Eingeschränkte Farbgebung von Grafiken

Mohammad Al-Turkistany
quelle