Mengurangi masalah faktorisasi bilangan bulat menjadi masalah NP-Lengkap

17

Saya berjuang untuk memahami hubungan antara NP-Intermediate dan NP-Complete. Saya tahu bahwa jika P! = NP berdasarkan Teorema Ladner ada kelas bahasa dalam NP tetapi tidak dalam P atau NP-Lengkap. Setiap masalah dalam NP dapat direduksi menjadi masalah NP-Complete, namun saya belum melihat contoh untuk mengurangi dugaan masalah NPI (seperti faktorisasi bilangan bulat) menjadi masalah NP-Complete. Adakah yang tahu contoh ini atau pengurangan NPC-> NPC lainnya?

np-complete reductions factoring Nathan Jordan
sumber
4
Dengan definisi kelengkapan NP, setiap masalah dalam NP dapat direduksi menjadi masalah NP-complete. Secara khusus, teorema Cook menunjukkan bahwa SAT adalah NP-complete, dan memberi Anda "secara eksplisit" pengurangan tersebut.
Yuval Filmus
1
@YuvalFilmus Saya mengerti bahwa ada formalisasi bahwa metode seperti itu ada, namun saya sedang mencari pendekatan algoritmik yang lebih konkret mirip dengan, katakanlah pengurangan masalah Hamiltonian Cycle ke masalah Traveling Salesman. Di mana Anda dapat mengatur semua bobot tepi menjadi 1 dan menjalankan TSP pada grafik dan memeriksa apakah jarak yang ditempuh lebih besar dari | E |. Sesuatu seperti itu kurasa.
Nathan Jordan

Jawaban:

11

Sebagai contoh, ada pengurangan klasik anjak piutang ke SAT yang juga merupakan sumber dari kejadian-kejadian SAT yang dianggap "sulit". Pada dasarnya orang menggunakan ide EE untuk perkalian biner yang dikodekan ke dalam sirkuit SAT. Pikirkan perkalian biner sebagai tambahan dari serangkaian perkalian bergeser ke kiri, masing-masing "bertopeng" (ANDed) oleh bit-bit pengali. Penambahan dapat dilakukan oleh rangkaian penambahan biner yang merupakan serangkaian full adders.

Sarjana yang berbakat dapat membangun algoritma ini. Saya tidak tahu di mana itu pertama kali diusulkan atau diterapkan dalam literatur. Saya akan tertarik mendengar referensi.

Lihat misalnya Satisfy This: Sebuah Upaya dalam Memecahkan Faktorisasi Perdana menggunakan Pemecah Kepuasan oleh Stefan Schoenmackers dan Anna Cavender yang menjabarkannya secara rinci. Juga tantangan SAT DIMACS dimulai pada akhir 90-an memiliki contoh anjak yang dihasilkan oleh beberapa peneliti tetapi mungkin algoritma tidak ditulis secara terpisah di sebuah makalah selama era itu.

ay
sumber
1
karena tautan kertas sekarang dilarang 403
vzn
2
Mengenai paragraf kedua Anda: Teorema Cook menunjukkan bahwa masalah apa pun dalam NP dapat dikurangi menjadi SAT.
Yuval Filmus
1
benar, bukti Cook adalah bukti keberadaan teoritis umum dan ada lebih banyak konversi langsung / khusus / algoritma yang sering dibangun antara masalah lengkap NP (biasanya dengan "overhead" yang lebih baik). mengacu pada yang terakhir.
vzn
11

Untuk lebih jelasnya, Integer Factorization tidak dikenal sebagai NP-intermediate, hanya diduga didasarkan pada kurangnya bukti NP-kelengkapan atau algoritma polinomial-waktu (meskipun banyak pekerjaan yang dimasukkan ke dalam keduanya). Saya tidak tahu ada masalah alami (yaitu tidak dibangun oleh Ladner untuk buktinya) yang pasti NP-intermediate jika P dan NP berbeda.

Oke, setelah disclaimer itu, Graph Isomorphism adalah kandidat lain untuk masalah NP-intermediate alami. Ada pengurangan waktu polinomial sederhana dari itu menjadi Subgraph Isomorphism - biarkan grafiknya tetap sama! Graph Isomorphism hanyalah kasus khusus dari Subgraph Isomorphism di mana kedua grafik memiliki ukuran yang sama. Sentuhan terakhir adalah Subgraph Isomorphism adalah NP-complete.

Terlepas dari itu, tentu saja selalu ada pengurangan yang tidak terlalu informatif yang dijanjikan oleh Teorema Cook-Levin , kami tahu bahwa setiap masalah NP-intermediate memiliki beberapa Mesin Turing polinomial waktu nondeterministik yang memutuskannya, dan kami dapat mengubahnya menjadi turunan dari SAT (hanya harus membangun TM!).

Luke Mathieson
sumber