Was ist die UG-Härte und wie unterscheidet sie sich von der NP-Härte, basierend auf der einzigartigen Spiel-Vermutung?

22

Es gibt viele Unannäherungsergebnisse, die auf der Vermutung einzigartiger Spiele beruhen. Beispielsweise,

Unter der Annahme der einzigartigen Spielvermutung ist es NP-schwer, das maximale Schnittproblem innerhalb eines Faktors R für jede Konstante R > R GW anzunähern .

(Hier ist R GW = 0.878… das Näherungsverhältnis des Goemans-Williamson-Algorithmus.)

Einige Leute bevorzugen jedoch den Begriff " UG-hard " als:

Es ist UG-schwer, das maximale Schnittproblem innerhalb eines Faktors R für jede Konstante R > R GW anzunähern .

Ist die letztere nur eine Abkürzung für die erstere, oder bedeuten sie unterschiedliche Aussagen?

Tsuyoshi Ito
quelle
+1 Sehr schön. Vielen Dank an Tsuyoshi, der Licht in dieses wichtige Konzept der Komplexitätstheorie gebracht hat.
Mohammad Al-Turkistany

Antworten:

15

Eine frühere Version dieser Antwort wurde ursprünglich von NicosM als Antwort auf die Frage „ Konsequenzen einzigartiger Spiele als NPI-Problem “ veröffentlicht. Da sich herausstellte, dass es nicht antwortete, was er fragen wollte, habe ich es auf diese Frage verschoben.

Kurze Antwort: Sie bedeuten unterschiedliche Aussagen. Das letztere impliziert das erstere, aber das erstere impliziert nicht notwendigerweise das letztere.

Lange Antwort: Erinnern Sie sich daran, dass das einzigartige Spielproblem das folgende Versprechungsproblem ist.

Einzigartiges Spielproblem mit den Parametern k ∈ℕ und ε , δ > 0 (1− ε > δ )
Instanz : Ein für zwei Spieler einmaliges Spiel G mit der Etikettengröße k .
Ja-Versprechen : G hat einen Wert von mindestens 1− ε .
Kein Versprechen : G hat einen Wert von höchstens δ .

Die Vermutung für einzigartige Spiele lautet:

Einzigartige Spielevermutung. Für alle Konstanten ε und δ existiert eine Konstante k, so dass das eindeutige Spielproblem mit den Parametern k , ε und δ NP-vollständig ist.

Betrachten Sie die Ergebnisse der folgenden Form:

(1) Unter der Annahme der einzigartigen Spielevermutung ist Problem X NP-schwer.

(Ein Beispiel für X ist das Problem der Approximation des maximalen Schnitts innerhalb eines konstanten Faktors R > R GW .)

Die meisten (wenn nicht alle) Ergebnisse des Formulars (1) beweisen tatsächlich die folgende Tatsache:

(2) Es gibt Konstanten & egr; und & dgr; so dass für jeden Konstante k , das einzigartige Spielproblem mit Parametern k , ε und δ zu reduzierbar ist X .

Es ist leicht zu überprüfen, dass (2) (1) impliziert. (2) impliziert jedoch mehr als (1): Nehmen wir zum Beispiel an, wir können eines Tages beweisen, dass eine Variante der einzigartigen Spielvermutung, bei der "NP-vollständig" durch " GI- hart" ersetzt wird, (2) impliziert dieses X ist auch GI-hart. (1) impliziert dies nicht. Dies ist der Grund, warum einige Leute der Ansicht sind, dass Aussage (1) nicht der beste Weg ist, um den Satz zu formulieren: (1) ist schwächer als das, was tatsächlich bewiesen wird, und der Unterschied könnte wichtig sein.

Obwohl (2) eine genauere Aussage darüber ist, was bewiesen ist, ist es eindeutig mundvoll. Deshalb haben sich die Leute eine Abkürzung ausgedacht: „Problem X ist UG-schwer“ ist eine Abkürzung für (2).

Tsuyoshi Ito
quelle
8
Dies scheint analog zu den beiden Aussagen zu sein: "(1) Angenommen, P! = NP, hat X keinen polynomiellen Zeitalgorithmus" und "(2) X ist NP-hart". (2) impliziert (1), aber (1) impliziert nicht (2). In der Praxis beweisen wir normalerweise (2), obwohl wir häufig (1) sagen, um die Bedeutung des Beweises für Personen zu erklären, die mit der NP-Härte nicht vertraut sind.
Robin Kothari
1
@ TsuyoshiIch überlege dir, deine eigene Antwort zu akzeptieren :). Es ist eigentlich ermutigt, und dies ist eine gute Referenz für zukünftige Googler.
Suresh Venkat
@ Suresh: Danke. Ich werde es wahrscheinlich tun, aber das System erfordert, dass ich 48 Stunden nach dem Posten der Frage warte, bevor ich meine eigene Antwort akzeptiere.
Tsuyoshi Ito
@ TsuyoshiIto: Ah, das habe ich nicht gemerkt. hört sich gut an.
Suresh Venkat
@ TsuyoshiIto: schöne klare Antwort! Es tut mir leid, dass ich Ihrer Bitte nicht nachgekommen bin, meine Kommentare als Antwort auf die andere Frage zu geben: Ich war fleißig, teils faul, teils hatte ich nicht das Gefühl, dass die überarbeitete Frage überhaupt eine Frage war.
Sasho Nikolov