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