Apa itu kekerasan UG, dan apa bedanya dengan kekerasan NP berdasarkan dugaan game yang unik?

Ada banyak hasil yang tidak dapat diperkirakan yang bergantung pada dugaan game yang unik. Sebagai contoh,

Dengan asumsi dugaan permainan yang unik, NP-sulit untuk memperkirakan masalah pemotongan maksimum dalam faktor R untuk setiap R > R _{GW yang} konstan .

(Di sini R _GW = 0,878 ... adalah rasio perkiraan dari algoritma Goemans-Williamson.)

Namun, beberapa orang lebih suka menggunakan istilah " keras-UG " sebagai:

Sangat sulit untuk memperkirakan masalah pemotongan maksimum dalam faktor R untuk setiap R > R _{GW yang} konstan .

Apakah yang terakhir hanya singkatan untuk yang pertama, atau apakah itu berarti pernyataan yang berbeda?

Versi sebelumnya dari jawaban ini pada awalnya diposting sebagai jawaban atas pertanyaan " Konsekuensi Game Unik menjadi masalah NPI " oleh NicosM. Karena ternyata itu tidak menjawab apa yang ingin dia tanyakan, saya memindahkannya ke pertanyaan ini.

Jawaban singkat: Mereka berarti pernyataan yang berbeda. Yang terakhir menyiratkan yang pertama, tetapi yang pertama tidak selalu berarti yang kedua.

Jawaban panjang: Ingatlah bahwa masalah game yang unik adalah masalah janji berikut.

Unik masalah game dengan parameter k ∈ℕ dan ε , δ > 0 (1- ε > δ )
Instance : Sebuah dua pemain satu putaran permainan yang unik G dengan ukuran label k .
Ya-janji : G memiliki nilai setidaknya 1− ε .
Tanpa janji : G memiliki nilai paling banyak δ .

Dugaan game unik ini:

Dugaan game yang unik. Untuk semua konstanta ε dan δ , terdapat konstanta k sedemikian sehingga masalah gim unik dengan parameter k , ε , dan δ adalah NP-complete.

Pertimbangkan hasil dari formulir berikut:

(1) Dengan asumsi dugaan game unik, masalah X adalah NP-hard.

(Contoh X adalah masalah perkiraan pemotongan maksimum dalam beberapa faktor konstan R > R _GW .)

Sebagian besar (jika tidak semua) dari hasil formulir (1) benar-benar membuktikan fakta berikut:

(2) Ada ada konstanta ε dan delta sehingga untuk setiap konstan k , masalah permainan yang unik dengan parameter k , ε , dan δ dapat direduksi menjadi X .

Sangat mudah untuk memverifikasi bahwa (2) menyiratkan (1). Namun, (2) menyiratkan lebih dari (1): misalnya, anggaplah bahwa suatu hari kita dapat membuktikan bahwa varian dari permainan unik dugaan di mana "NP-complete" diganti dengan " GI -hard." Kemudian (2) menyiratkan bahwa X juga GI-keras. (1) tidak menyiratkan ini. Inilah mengapa beberapa orang menganggap bahwa pernyataan (1) bukan cara terbaik untuk menyatakan teorema: (1) lebih lemah dari apa yang sebenarnya terbukti, dan perbedaannya mungkin penting.

Meskipun (2) adalah pernyataan yang lebih akurat tentang apa yang terbukti, itu jelas tidak berarti. Inilah sebabnya mengapa orang membuat sebuah steno untuknya: “Masalah X adalah UG-keras” adalah singkatan untuk (2).