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

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?

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).