Apakah setiap masalah NP memiliki formulasi ILP berukuran poli?

14

Karena Integer Linear Programming adalah NP-complete, ada pengurangan Karp dari setiap masalah di NP untuk itu. Saya pikir ini menyiratkan bahwa selalu ada formulasi ILP berukuran polinomial untuk setiap masalah dalam NP.

Tetapi saya telah melihat makalah tentang masalah NP spesifik di mana orang menulis hal-hal seperti "ini adalah formulasi ukuran-poli pertama" atau "tidak ada formulasi ukuran-poli yang diketahui". Itu sebabnya saya bingung.

complexity-theory np-complete reductions linear-programming andy
sumber
8
Anda harus menunjukkan contoh atau memberikan penawaran yang lebih lengkap;)
hugomg
1
Ada pengurangan polinomial dari setiap masalah NP-complete ke setiap masalah NP-complete lainnya. Namun, hanya karena kita tahu keberadaannya tidak berarti kita tahu bagaimana membangunnya.
Joe
3
@Baiklah, kami tahu cara mengurangi masalah dalam NP menjadi 3-sat, dan juga setiap bukti masalah NP-complete praktis berasal dari rantai pengurangan dari 3-sat, sehingga Anda selalu dapat menyusun pengurangan dari masalah NPC yang diberikan ke ada yang lain.
andy
10
@Anly bukankah Anda hanya menjawab pertanyaan Anda dengan komentar itu? Anda tahu setiap instance masalah NP dapat ditulis sebagai instance 3-SAT yang dipolisiasi, dan Anda tahu bahwa instance 3-SAT dapat ditulis sebagai instance ILP yang dipolisiasi, dan polinom yang diterapkan ke polinom adalah polinomial lain ... apa lagi yang Anda lakukan harapkan dari sebuah jawaban?
Artem Kaznatcheev
2
Ketika seseorang mengatakan bahwa ini adalah formulasi poly-size pertama, yang mereka maksud adalah bahwa itu adalah formulasi pertama yang diberikan secara eksplisit . Pengurangan yang diperoleh melalui SAT (bahkan jika seseorang mengurus semua detail) tidak terlihat bagus dan sulit untuk dikerjakan. Kami biasanya menginginkan formulasi yang alami dan mudah digunakan.
Kaveh

Jawaban:

5

Jawaban ini sebagian besar adalah rekap dari komentar pada pertanyaan di atas.

Jika masalah adalah NP-lengkap, memang bisa dikurangi menjadi ILP, dengan menggunakan pengurangan Karp (- Joe, andy). Klaim "formulasi ukuran polinomial" dari satu masalah ke masalah lain, kemungkinan dimaksudkan sebagai formulasi yang lebih langsung, sebagai lawan dari beberapa pengurangan melalui SAT (- Kaveh).

Realz Slaw
sumber
1

Iya. Setiap masalah NP memiliki formulasi ILP berukuran polinomial.

Inilah sebabnya. Setiap masalah NP memiliki formulasi berukuran polinomial sebagai instance dari SAT. Selain itu, semua operator boolean yang biasa - logis ATAU, logis DAN, TIDAK logis, dll. - dapat dinyatakan dalam ILP, menggunakan jumlah variabel dan ketidaksetaraan per operator boolean yang konstan. Lihat Mengekspresikan operasi logika boolean dalam zero-one integer linear programming (ILP) untuk perincian cara melakukannya. Dengan demikian, kita mendapatkan paling banyak ledakan berukuran konstan ketika pergi dari SAT ke ILP. Ini menyiratkan bahwa ada formulasi berukuran polinomial dari setiap masalah NP sebagai masalah ILP.

DW
sumber