Czym jest twardość UG i czym różni się od twardości NP w oparciu o unikalną hipotezę gier?

Istnieje wiele niedopuszczalności wyników, które opierają się na unikalnym założeniu gier. Na przykład,

Zakładając unikalną hipotezę gier, NP jest trudne do przybliżenia maksymalnego problemu cięcia w ramach współczynnika R dla dowolnej stałej R > R _GW .

(Tutaj R _GW = 0,878… jest współczynnikiem przybliżenia algorytmu Goemans – Williamson.)

Jednak niektórzy wolą używać terminu „ UG-hard ” jako:

UG-trudno jest oszacować maksymalny problem cięcia w ramach współczynnika R dla dowolnej stałej R > R _GW .

Czy to drugie jest tylko skrótem dla tych pierwszych, czy też oznaczają różne stwierdzenia?

Wcześniejsza wersja tej odpowiedzi została pierwotnie opublikowana przez NicosM jako odpowiedź na pytanie „ Konsekwencje unikatowych gier będących problemem NPI ”. Ponieważ okazało się, że nie odpowiada na to, o co chciał zapytać, przeniosłem to na to pytanie.

Krótka odpowiedź: oznaczają różne stwierdzenia. To drugie oznacza pierwsze, ale drugie niekoniecznie implikuje drugie.

Długa odpowiedź: przypomnij sobie, że jedynym problemem związanym z grą jest następujący problem.

Unikalny problem z parametrami k ∈ℕ i ε , δ > 0 (1− ε > δ )
Wystąpienie : Jednoczesna gra G dla dwóch graczy o rozmiarze etykiety k .
Tak, obietnica : G ma wartość co najmniej 1 ε .
Bez obietnicy : G ma wartość co najwyżej δ .

Unikalna hipoteza gier mówi:

Unikalna hipoteza gier. Dla wszystkich stałych ε i δ istnieje stała k, tak że unikalny problem z parametrami k , ε i δ jest NP-zupełny.

Rozważ wyniki następującego formularza:

(1) Zakładając unikalną hipotezę gier, problem X jest trudny do rozwiązania.

(Przykładem X jest problem aproksymacji maksymalnego cięcia w ramach pewnego stałego współczynnika R > R _GW .)

Większość (jeśli nie wszystkie) wyników formularza (1) faktycznie potwierdza następujący fakt:

(2) Istnieje stałe ε i hemibursztynianu , że dla każdej stałej K , unikalny problemu gier z parametrów k , ε i hemibursztynianu sprowadza się do X .

Łatwo jest zweryfikować, że (2) implikuje (1). Jednak (2) oznacza więcej niż (1): na przykład załóżmy, że pewnego dnia możemy udowodnić, że wariant unikalnej gry zakłada, że ​​„NP-complete” jest zastąpione przez „ GI- twarde”. Następnie (2) oznacza że X jest również trudne do oznaczenia. (1) nie implikuje tego. Dlatego niektórzy uważają, że stwierdzenie (1) nie jest najlepszym sposobem na stwierdzenie twierdzenia: (1) jest słabsze niż to, co faktycznie udowodniono, a różnica może być istotna.

Chociaż (2) jest dokładniejszym stwierdzeniem tego, co zostało udowodnione, jest wyraźnie kęs. Oto dlaczego ludzie wymyślili na to skrót: „Problem X jest trudny dla UG” to skrót dla (2).