Pengurangan banyak-orang paling lambat?

Ketika kita ingin membuktikan bahwa adalah -Lengkap, maka pendekatan standar untuk menunjukkan waktu polinomial komputasi pengurangan banyak-salah satu yang dikenal masalah -Lengkap untuk . Dalam konteks ini kita tidak perlu terikat ketat pada waktu pengurangan berjalan. Itu sudah cukup untuk telah setiap polinomial terikat, yang memungkinkan bahwa mungkin mungkin memiliki gelar yang sangat tinggi. $L\in \bf NP$ $\bf NP$ $\bf NP$ $L$

Namun demikian, untuk masalah alam, ikatan biasanya polinomial derajat rendah (mari kita definisikan rendah sebagai sesuatu dalam digit tunggal). Saya tidak mengklaim bahwa ini harus selalu menjadi masalah, tetapi saya tidak mengetahui contoh tandingan.

Pertanyaan: Apakah ada contoh tandingan? Itu akan menjadi banyak-satu pengurangan polytime yang dihitung antara dua masalah lengkap alami , sehingga tidak ada pengurangan lebih cepat diketahui untuk kasus yang sama, dan waktu berjalan polinomial yang paling dikenal adalah polinomial tingkat tinggi . $NP$

Catatan: Eksponen besar, atau bahkan besar, kadang-kadang diperlukan untuk masalah alami di , lihat Algoritma waktu polinomial dengan eksponen / konstanta besar . Saya bertanya-tanya apakah hal yang sama juga terjadi pada pengurangan di antara masalah alam? $P$

cc.complexity-theory reductions np-complete Andras Farago
sumber

Makalah ini mungkin relevan. Kelengkapan NP di bawah reduksi sangat terbatas (misalnya AC0 atau logspace) menarik, karena sebagian besar reduksi secara intuitif "berbasis gadget", yang berasal dari kenyataan bahwa perhitungan adalah fenomena lokal

Joe Bebel

Kami biasanya berurusan dengan pengurangan yang mengubah sebuah contoh dari SAT (atau masalah NPC sederhana) ke sebuah contoh dari

. Tetapi berpikir dengan cara sebaliknya

(yaitu-di dunia nyata-coba memecahkan masalah menggunakan pemecah SAT) mengarah pada pengurangan waktu polinomial dengan eksponen yang memalukan :-). Misalnya, kelas masalah yang saya alami, muncul dari game lengkap PSPACE, ketika Anda menambahkan beberapa kendala (waktu, jumlah gerakan, kunjungan terbatas ke lokasi, ...) yang membuatnya jatuh dalam NP, dan kemudian cobalah untuk menyelesaikannya dengan SAT solver, yaitu menemukan pengurangan yang efisien untuk SAT.

L

$L$

L \leq_{p} S A T

$L \leq_p SAT$

Marzio De Biasi

Saya ingat kami memiliki pertanyaan terkait tentang masalah NP alami yang memerlukan sertifikat besar (yaitu kompleksitas bukti besar yang lebih rendah), tetapi saya tidak dapat menemukannya.

Kaveh

@Kaveh: satu adalah milikku: " Masalah NP-lengkap alami dengan saksi" besar " " :-)

Marzio De Biasi

Dengan teorema hierarki ada masalah dalam NP dengan waktu nondeterministic batas bawah yang merupakan polinomial tingkat besar sewenang-wenang. Memilih beberapa masalah yang membutuhkan setidaknya

langkah nondeterministic, untuk

. Misalkan banyak-satu pengurangan dari masalah ini ke SAT ada yang menggunakan paling

waktu. Maka instance SAT bisa tidak lebih besar dari

bits. Ini kemudian dapat diputuskan menggunakan paling banyak

langkah nondeterministic. Karenanya

n^{d}

$n^d$

d \geq 20

$d \ge 20$

n^{c}

$n^c$

n^{c}

$n^c$

n^{2 c}

$n^{2c}$

c \geq d / 2 \geq 10

$c \ge d/2 \ge 10$ . Jika Anda ingin masalah menjadi alami juga, maka Anda pada dasarnya meminta masalah alami tidak dalam NTIME (

n^{d}

$n^d$

András Salamon

Allender menyarankan jawabannya adalah tidak:

Tampaknya tidak ada pasangan masalah NP-lengkap alami A dan B yang diketahui, di mana pengurangan dari A ke B diketahui membutuhkan lebih dari waktu linier (bahkan dengan asumsi bahwa P NP) $\ne$

Referensi:

E. Allender dan M. Koucký, Memperkuat batas bawah dengan cara reduksi diri . Jurnal ACM 57, 3, Pasal 14 (Maret 2010).

Mohammad Al-Turkistany
sumber

Bisakah Anda memberikan tautan ke makalah tempat Allender menulis ini, atau referensi?

Andras Farago

@AndrasFarago Tautan disediakan. Klik pada Allender :).

Mohammad Al-Turkistany

Maaf, saya ketinggalan tautan. Setelah melihat ke kertas, saya menemukan pernyataan lain yang cukup menarik: "tidak ada masalah NP-lengkap alami yang diketahui berada di luar NTIME (n)." (Itu dalam kalimat segera sebelum bagian yang dikutip.)

Andras Farago

Saya menyarankan beberapa kebijaksanaan ringan ketika menafsirkan pernyataan ini. Ada beberapa kasus di mana hanya, katakanlah, pengurangan kuadratik diketahui. Misalnya, pengurangan ke versi planar dari masalah NP-complete dapat menggunakan jumlah kuadrat gadget crossover. Batas bawah rumit dan banyak hal "tidak diketahui perlu".

Joe Bebel

@ JoBebel Saya setuju bahwa kebijaksanaan diperlukan ketika menafsirkan pernyataan ini. Sebagai contoh, dalam pernyataan bahwa "tidak ada masalah NP-lengkap alami diketahui berada di luar NTIME (n)," penulis mungkin memiliki interpretasi yang lebih sempit dari "alami" dalam pikiran. Mungkin mereka berarti sesuatu seperti ini: masalah alam adalah salah satu yang orang mungkin benar-benar ingin memecahkan atas dasar motivasi praktis.

Andras Farago

Pengurangan banyak-orang paling lambat?

Jawaban: