Teknik untuk menunjukkan masalah itu dalam kekerasan "limbo"

Diberikan masalah baru di yang kompleksitas sebenarnya ada di antara dan NP-complete, ada dua metode yang saya tahu yang mungkin digunakan untuk membuktikan bahwa menyelesaikan ini sulit: $\mathsf{NP}$ $\mathsf{P}$

Tunjukkan bahwa masalahnya adalah GI-complete (GI = Graph Isomorphism)
Tunjukkan bahwa masalahnya ada di . Dengan hasil yang diketahui, hasil seperti itu menyiratkan bahwa jika masalahnya adalah NP-lengkap, maka PH runtuh ke tingkat kedua. Sebagai contoh, protokol terkenal untuk Graph Nonisomorphism melakukan hal ini. $\mathsf{co-AM}$

Apakah ada metode lain (mungkin dengan "kekuatan keyakinan" yang berbeda) yang telah digunakan? Untuk jawaban apa pun, diperlukan contoh tempat penggunaannya: jelas ada banyak cara yang bisa dilakukan untuk menunjukkan ini, tetapi contoh membuat argumen lebih meyakinkan.

cc.complexity-theory np-hardness graph-isomorphism np-intermediate Suresh Venkat
sumber

Jika masalah tampaknya cukup sulit, tetapi Anda tidak dapat membuktikan bahwa itu adalah NPC, pemeriksaan cepat adalah untuk menghitung jumlah string panjang n dalam bahasa: jika set jarang, itu tidak mungkin menjadi NPC (jika tidak, P = NP oleh teorema Mahaney) ... jadi lebih baik mengarahkan usaha untuk membuktikan bahwa itu ada di P :-) :-) Contoh dari blog Fortnow & Gasarch : {(n, k): ada cara untuk mempartisi { 1, ..., n} ke dalam maksimal k kotak sehingga tidak ada kotak yang memiliki x, y, z dengan x + y = z}

Marzio De Biasi

@MarzioDeBiasi terdengar seperti jawaban untuk saya.

Sasho Nikolov

Ada dua bagian demonstrasi seperti itu: menunjukkan kesulitan menempatkan masalah di BPP, dan menunjukkan kesulitan menempatkan masalah di kelas NP-complete. (Ingat bahwa kelengkapan-GI hanya berarti "ada di GI dan sulit-GI".)

$\:$

$\;\;\;$

+1 untuk Ricky Demer; kami mungkin ingin memiliki daftar metode untuk bagian pertama.

Pteromys

Untuk masalah dalam FNP tanpa versi keputusan yang jelas dalam NP, PPAD adalah kelas yang berguna (dan terus bertambah) untuk dipertimbangkan. Masalah lengkap PPAD mencakup banyak masalah tentang menemukan titik tetap, misalnya Nash equilibria. Daftar Shiva bermanfaat: cs.princeton.edu/ ~kintali

András Salamon

Jawaban:

Menunjukkan bahwa masalah Anda ada dalam coAM (atau SZK) memang merupakan salah satu cara utama untuk mengemukakan bukti "kekerasan limbo." Tapi selain itu, ada beberapa yang lain:

Tunjukkan bahwa masalah Anda ada di NP ∩ coNP. (Contoh: Anjak piutang.)
Tunjukkan bahwa masalah Anda dapat diselesaikan dalam waktu yang seminimal mungkin. (Contoh: Dimensi VC, mendekati game gratis.)
Tunjukkan bahwa masalah Anda tidak lebih sulit daripada membalikkan fungsi satu arah atau menyelesaikan NP rata-rata. (Contoh: Banyak masalah dalam kriptografi.)
Tunjukkan bahwa masalah Anda berkurang menjadi (misalnya) Permainan Unik atau Ekspansi Set Kecil.
Tunjukkan bahwa masalah Anda ada di BQP. (Contoh: Anjak piutang, meskipun tentu saja itu juga dalam NP ∩ coNP.)
Singkirkan kelas besar pengurangan kelengkapan NP. (Contoh: Masalah Minimisasi Sirkuit, dipelajari oleh Kabanets dan Cai.)

Saya yakin ada orang lain yang saya lupa.

Scott Aaronson
sumber

Itu daftar yang sangat bagus, Scott!

Suresh Venkat

Hanya ingin tahu ... teknik mana dari yang menunjukkan bahwa masalahnya tidak mungkin dipecahkan dalam waktu polinomial (atau RP, atau BPP)? Saya tidak melihat ada yang tampaknya melakukan ini.

Philip White

Philip: Anda benar, mereka tidak. Untuk menambahkan bukti bahwa masalah NP tertentu tidak dalam P, semuanya bermuara pada (1) mencoba memasukkannya ke dalam P dan gagal, dan / atau (2) mengurangi masalah lain yang orang gagal masukkan ke P untuk masalah itu.

Scott Aaronson

$n$

Contohnya adalah masalah mempartisi angka menjadi k-box (dari blog Fortnow & Gasarch, sumber asli: Doctor Ecco's Cyberpuzzles ):

$\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

Marzio De Biasi
sumber

Berikut adalah tiga tambahan pada daftar Scott:

Tunjukkan masalah Anda dalam beberapa P. Ini berarti bahwa jumlah solusi dibatasi oleh beberapa polinomial. (Contoh: Masalah Turnpike). Tidak ada masalah NP-complete yang diketahui dalam beberapa P. (tidak mungkin kecuali beberapa P = NP).
$LOGNP$ $NP[log^2n]$
$2^{n^{\epsilon}}$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

$coNP ⊆ NP/poly$

Mohammad Al-Turkistany
sumber

Atau bahkan dalam UP (bukan hanya FewP)!

Joshua Grochow