Apakah ada masalah NP-complete dengan solusi waktu yang diharapkan polinomial?

24

Apakah ada masalah NP-lengkap yang diketahui algoritma yang waktu berjalannya diharapkan polinomial (untuk beberapa distribusi yang masuk akal atas contoh)?

Jika tidak, adakah masalah yang keberadaan algoritme seperti itu telah ditetapkan?

Atau apakah keberadaan algoritma seperti itu menyiratkan adanya algoritma waktu polinomial deterministik?

cc.complexity-theory np-hardness Steve Kroon
sumber

6

Saya tidak begitu mengerti apa pertanyaannya. Apakah Anda meminta hasil kasus rata-rata untuk masalah NP-hard atau Anda bertanya apakah kami dapat menyelesaikan masalah NP-hard dalam kasus terburuk dalam waktu polinomial yang diharapkan?

Moritz

2

Apa yang Anda maksud dengan "waktu berlari yang diharapkan"? Apakah Anda mengambil ekspektasi atas beberapa distribusi input acak (karena sebagian besar jawaban tampaknya berpikir), atau lebih dari distribusi bit acak yang digunakan oleh algoritma (arti biasa untuk algoritma acak), atau keduanya?

Jeffε

@Moritz: Saya bertanya tentang hasil kasus rata-rata untuk masalah NP-hard. Memecahkan masalah NP-hard dalam kasus terburuk dalam waktu polinomial yang diharapkan tampaknya hasil yang lebih kuat bagi saya, jadi saya akan tertarik dengan hasil seperti itu juga. @ Jeff Aku berbicara tentang waktu yang diharapkan dan beberapa distribusi atas contoh. Jika algoritma ini diacak, orang akan mengambil ekspektasi atas bit acak juga. Tetapi pertanyaan saya bukan terutama tentang algoritma acak.

Steve Kroon

3

Teknik padding sederhana memberi Anda cara untuk membangun ini dari masalah apa pun.

$L$ $NP$ $O(2^{n})$ $K$

K = {1^{n} x | ‖ x ‖ = n and x \in L}

$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$

K

$K$

n

$n$

1^{n}

$1^n$

x \overset{?}{\in} L

$x\overset{?}{\in}L$

y \in_{R} {0, 1}^{2 n}

$y\in_R \{0,1\}^{2n}$

y \overset{?}{\in} K

$y\overset{?}{\in}K$

\frac{1}{2^{2 n}} (2^{n} \cdot 2^{n} + (2^{2 n} - 2^{n}) HAI (n)) = 1 + (1 - \frac{1}{2^{n}}) HAI (n) \in HAI (n) .

$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$

$K$ adalah -Lengkap. Pengurangan dari adalah: $NP$ $L$

x \in {0, 1}^{n} \mapsto 1^{n} x

$x\in \{0,1\}^n \mapsto 1^nx$

Pengganti Vinkhuijzen
sumber

13

Ada algoritma waktu polinomial untuk menemukan siklus Hamilton pada grafik acak, yang berhasil secara asimptotik dengan probabilitas yang sama dengan siklus Hamilton. Tentu saja, masalah ini NP-hard dalam kasus terburuk.

Mereka juga menunjukkan bahwa algoritma pemrograman dinamis yang selalu dijamin untuk menemukan siklus Hamilton, jika ada, memiliki waktu berjalan polinomial yang diharapkan, jika distribusi input seragam secara acak di atas set semua grafik vertex. $n$

Referensi: "Algoritma untuk menemukan siklus Hamilton dalam grafik acak"

Bollobas, Fenner, Frieze

http://portal.acm.org/citation.cfm?id=22145.22193

Aaron Roth
sumber

10

Mengenai pertanyaan terakhir Anda tentang apakah keberadaan algoritma kasus rata-rata yang baik akan menyiratkan adanya algoritma kasus terburuk yang baik: ini adalah pertanyaan terbuka utama yang sangat menarik bagi cryptographers. Kriptografi membutuhkan masalah yang rata-rata sulit, tetapi kriptografi ingin mendasarkan konstruksi mereka pada asumsi minimum yang mungkin, sehingga sangat menarik untuk menemukan masalah di mana kekerasan kasus rata-rata terbukti sama dengan kekerasan kasus terburuk.

Beberapa masalah kisi diketahui memiliki pengurangan kasus terburuk hingga rata-rata. Lihat, misalnya, Menghasilkan contoh sulit dari masalah kisi oleh Ajtai, dan artikel survei oleh Micciancio.

Ian
sumber

9

Pada dasarnya, Max 2-CSP pada variabel dan kendala yang dipilih secara acak dapat diselesaikan dalam waktu linear yang diharapkan (lihat referensi di bawah ini untuk perumusan hasil yang tepat). Perhatikan bahwa Max 2-CSP tetap NP-keras ketika jumlah klausa sama dengan jumlah variabel seperti NP-keras jika grafik kendala instance memiliki tingkat maksimum paling banyak 3 dan Anda dapat menambahkan beberapa variabel dummy untuk mengurangi rata-rata tingkat ke 2. $n$ $n$

Referensi:

Alexander D. Scott dan Gregory B. Sorkin. Memecahkan contoh acak Max Cut dan Max 2-CSP yang jarang secara acak dalam waktu yang diharapkan secara linier. Sisir. Mungkin. Comput., 15 (1-2): 281-315, 2006. Preprint

Serge Gaspers
sumber

2

Saya tidak melihat bagaimana pernyataan Anda cocok dengan klaim di koran. Makalah ini berbicara tentang penyelesaian Max 2-CSP jika grafik yang mendasari adalah grafik acak dalam model G (n, c / n) untuk beberapa c tetap, yang berarti bahwa itu adalah grafik pada n simpul di mana setiap tepi terjadi secara independen dengan probabilitas c / n, maka dengan harapan ada

edge (kendala) dalam instance. Tetapi jika Anda melakukan pengurangan NP-hardness untuk mendapatkan instance yang sulit dengan n simpul dan n edge, distribusi instance TIDAK akan mengikuti model

dan karenanya saya tidak akan mengatakan bahwa kertas tersebut menyelesaikan NP-hard. masalah.

Θ (n)

$\Theta(n)$

G (n, c / n)

$G(n,c/n)$

Bart Jansen

@ Bart: Saya mungkin salah paham pertanyaannya. Saya mengklaim bahwa Max 2-CSP dengan jumlah klausa linier adalah NP-hard, tetapi ada algoritma dengan waktu linier yang diharapkan memecahkan masalah ini untuk contoh acak.

Serge Gaspers

Pada dasarnya, jika saya memahami argumen Anda dengan benar, Anda mengatakan bahwa Max 2-CSP yang dilengkapi dengan distribusi G (n, c / n) pada grafik yang mendasarinya dapat diselesaikan dalam waktu linear yang diharapkan. Saya setuju dengan Bart dalam hal distribusi tampaknya tidak sepenuhnya "masuk akal" atau "alami" bagi saya, tetapi saya pikir itu menjawab pertanyaan saya secara memadai.

Steve Kroon

@Steve: Saya setuju.

Serge Gaspers

7

Ini tidak menjawab pertanyaan Anda sepenuhnya, tetapi untuk survei hasil pada contoh acak 3-SAT Anda dapat melihat ini: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Biasanya sulit untuk mendefinisikan apa yang sebenarnya dimaksud dengan "penyimpangan yang masuk akal". Anda dapat mengikuti tautan ini untuk membaca lebih lanjut tentang ini dalam survei "Kompleksitas waktu rata-rata" oleh Bogdanov dan Trevisan: http://arxiv.org/abs/cs/0606037 .

Grigory Yaroslavtsev
sumber

Terima kasih atas tautannya. Sayangnya hasil 3-SAT karya "dengan probabilitas tinggi" tidak cukup kuat (sejauh yang saya bisa lihat) untuk menegaskan permintaan saya. Saya setuju "distribusi yang masuk akal" bisa berbulu. Dalam hal ini, saya akan lebih suka jika distribusi tidak jelas dipilih sehingga "ruang contoh efektif" tidak hanya mengurangi masalah menjadi satu yang diketahui berada di P.

Steve Kroon

5

"Mewarnai Grafik Acak dalam Waktu Polinomial yang Diharapkan" oleh Amin Coja-Oghlan dan Anusch Taraz

$G \in G(n, p)$ $p < 1.01/n$ $O(√np)$

http://www.springerlink.com/content/87c17d4dacbrc0ma/

Joel Rybicki
sumber

Apakah ada masalah NP-complete dengan solusi waktu yang diharapkan polinomial?

Jawaban: