Masalah yang NP-lengkap di bawah pengurangan acak atau P / poli.

Dalam pertanyaan ini , kami tampaknya telah mengidentifikasi masalah alami yang NP-lengkap di bawah reduksi acak, tetapi mungkin tidak di bawah reduksi deterministik (meskipun ini tergantung pada asumsi yang tidak terbukti dalam teori bilangan yang benar). Apakah ada masalah lain yang diketahui? Apakah ada masalah alami yang NP-lengkap di bawah pengurangan P / poli, tetapi tidak diketahui berada di bawah pengurangan P?

cc.complexity-theory np-hardness big-list randomness reductions Peter Shor
sumber

SAT unik adalah

dengan reduksi acak.

N P

$NP$

Mohammad Al-Turkistany

Saya tidak melihat mengapa SAT Unik tidak boleh dianggap sebagai jawaban (meskipun itu tidak cukup seperti yang saya cari). Saya pikir ini dianggap sebagai masalah alami.

Peter Shor

Saya hanya ingin menambahkan bahwa masalah vektor terpendek untuk LLL di bawah norma

untuk pengurangan secara acak (kertas oleh Ajtai di sini ) adalah NP-Hard. Sejauh yang saya tahu itu tidak diketahui sebagai NP-Hard di bawah pengurangan non-acak, jadi itu tidak memenuhi kriteria Anda, tapi saya pikir itu harus disebutkan pula.

L_{2}

$L_2$

user834

@ Joshua: Dalam beberapa masalah NP-lengkap terkait dengan teka-teki (seperti Sudoku), keunikan solusi adalah asumsi alami. Saya kira ini membuat SAT dengan paling banyak satu solusi (saya lebih suka menyebutnya SAT ambigu) lebih alami daripada yang mungkin terlihat pertama kali.

Tsuyoshi Ito

Mengapa semua orang menulis jawaban dalam komentar? : P

Hsien-Chih Chang 張顯之

Jawaban:

Di bawah reduksi acak dengan probabilitas (dikenal juga sebagai -reducibility, pada pembahasan pengurangan acak melihat "Pada Unik satisfiability dan Acak Pengurangan") masalah $\frac{1}{2}$ $\gamma$

Dapat dibagi secara linier
Persamaan diophantine kuadratik biner

NP-complete, tetapi hal yang sama tidak diketahui untuk reduksi deterministik (sejauh yang saya tahu, untuk diskusi sedikit ketinggalan zaman tentang situasi ini lihat di sini ). -reducibility diperkenalkan di koran " reducibility, keacakan, dan intractibility " oleh Leonard Adleman dan Kenneth Manders (bukti untuk masalah di atas diusulkan juga ada). $\gamma$

Ada contoh lain seperti itu di " Katalog Kelas Kompleksitas ", tapi saya belum memeriksa apa yang diketahui tentang kelengkapan NP mereka di bawah reduksi deterministik.

Oleksandr Bondarenko
sumber

Seperti yang disarankan oleh Peter, saya mengubah komentar saya menjadi jawaban.

Valiant-Vazirani Teorema menyatakan bahwa jika Unik SAT kemudian . Untuk membuktikan teorema mereka, mereka menunjukkan bahwa masalah janji SAT Unik adalah dalam pengurangan acak. $\in P$ $NP=RP$ $NP$

[1] Valiant, Leslie; Vazirani, Vijay. "NP semudah mendeteksi solusi unik", Theoretical Computer Science, 47: 85-93

Mohammad Al-Turkistany
sumber

Seperti yang disarankan oleh Peter, saya mengubah komentar saya menjadi sebuah jawaban:

$L_2$ $NP$

pengguna834
sumber