Mengapa pemrograman linier dalam P tetapi pemrograman integer NP-hard?

35

Linear programming (LP) dalam P dan integer programming (IP) adalah NP-hard. Tetapi karena komputer hanya dapat memanipulasi angka dengan ketepatan yang terbatas, dalam praktiknya komputer menggunakan bilangan bulat untuk pemrograman linier. Karena itu, bukankah LP dan IP harus berada dalam kelas kompleksitas yang sama?

complexity-theory polynomial-time Sasha si Noob
sumber
7
Menambahkan sedikit ke jawaban jmite: Ada banyak kasus di mana kendala integralitas membuat masalah lebih sulit. Sebagai contoh masalah ransel fraksional dapat diselesaikan dalam waktu polinomial, meskipun masalah ransel bilangan bulat adalah NP-Hard. Jadi ini bukan hanya sesuatu yang benar untuk LP dan IP.
user340082710
7
Bahkan jika kita menganggap bahwa komputer melakukan operasi dengan bilangan bulat, maka itu tidak berarti bahwa solusi yang dikembalikan adalah bilangan bulat; itu bisa rasional, yaitu rasio dua bilangan bulat. Dan itu memberi lebih banyak fleksibilitas. Dan tentu saja, kita tidak selalu dapat mengubah solusi rasional menjadi solusi yang layak untuk IP. Secara umum, IP akan memiliki lebih banyak kendala pada variabel daripada hanya meminta solusi integral. Pikirkan program bilangan bulat . 0,1
megas
1
Tidak sulit untuk memanipulasi angka dengan ketelitian tak terbatas jika Anda mau, terutama ketika mereka rasional. Ketepatan yang terbatas hanyalah sebuah optimasi untuk mengurangi runtimes.
2
@Hurkyl "Tidak sulit untuk memanipulasi angka dengan ketepatan tak terbatas jika Anda mau, terutama ketika mereka rasional." Ada subset ketat dari bilangan real yang disebut angka yang dapat dihitung, yang mencakup rasional + angka seperti sqrt (2) dll ... dan didefinisikan sebagai himpunan bilangan yang dapat dihitung oleh mesin Turing. Mereka yang tidak termasuk di sana, tidak dapat, menurut definisi, dimanipulasi oleh komputer.
Sasha the Noob
1
@SashatheNoob Apa yang Anda katakan tidak benar-benar bertentangan dengan apa yang Hurkyl katakan. Nomor yang Dapat Dihitung tidak memiliki batas maksimum yang sudah ditentukan sebelumnya tentang seberapa tepat angka itu (itu secara sewenang-wenang diatur ke nilai apa pun yang Anda suka asalkan mesin turing memiliki cukup memori - maka presisi yang tak terbatas). Untuk mengatakan bahwa himpunan bagian dari Angka yang Dapat Dihitung mencakup semua angka yang rasional, Anda mengakui bahwa komputer dapat memanipulasi angka dengan ketepatan tak terbatas. (Pernyataan Hurkyl benar-benar benar. Fakta bahwa ketepatan terbatas untuk tipe data tertentu hanyalah sebuah pengoptimalan.)
BrainSlugs83

Jawaban:

9

Saya tidak dapat berkomentar karena memerlukan 50 rep, tetapi ada beberapa kesalahpahaman yang tersebar, terutama komentar Raphael "Secara umum, domain yang berkelanjutan berarti tidak ada kekuatan kasar (dan tidak ada heuristik yang pintar untuk mempercepatnya)."

Ini benar-benar salah. Poin kuncinya adalah cembung. Kecuali beberapa kualifikasi kendala teknis, meminimalkan fungsi cembung (atau memaksimalkan fungsi cekung) pada set cembung pada dasarnya sepele, dalam arti konvergensi waktu polinomial.

Secara longgar, Anda bisa mengatakan ada korespondensi antara kecemburuan masalah dalam optimasi "matematis" dan kelayakan algoritma serakah dalam optimasi "ilmu komputer". Ini dalam arti bahwa keduanya memungkinkan metode pencarian lokal. Anda tidak akan pernah harus melacak kembali dalam algoritma serakah dan Anda tidak akan pernah harus menyesali arah keturunan dalam masalah optimasi cembung. Peningkatan lokal pada fungsi tujuan akan SELALU membawa Anda lebih dekat ke optimal global.

Ini tidak demikian dalam kasus non-cembung. Di sini, mungkin ada global minimum, tetapi beberapa minimum lokal yang akan selalu ditarik oleh algoritma penurunan lokal, dengan cara yang sama dilakukan oleh algoritma serakah ketika diterapkan pada masalah NP. Terkadang mereka menemukan optimal yang sebenarnya, sebagian besar waktu tidak.

Benjamin Lindqvist
sumber
23

Jawaban singkatnya: karena Anda dapat menggunakan Integer untuk mensimulasikan Boolean untuk SAT , tetapi ketika Anda tidak membatasi diri Anda dengan ini, maka Anda tidak dapat benar-benar mensimulasikan SAT. Anda akan mendapatkan jawaban yang layak, tetapi itu tidak lagi membawa arti dalam hal apa pun contoh SAT yang Anda coba simulasikan.

Jawaban sulit untuk ini adalah kita tidak tahu bahwa mereka tidak berada dalam kelas kompleksitas yang sama. Tidak ada yang memiliki bukti bahwa . Jika kita memahami alasan yang lebih dalam mengapa masalahnya sangat berbeda, itu akan mengharuskan kita memahami mengapa kelas kompleksitasnya berbeda, yang tidak kita lakukan.P≠NP

Ya ampun
sumber
21

Alasan pemrograman linier adalah "efisien" adalah bahwa ruang solusi dapat diwakili oleh polihedron cembung tunggal. Jika seseorang mencoba untuk menemukan titik "tertinggi" pada polyhedron itu (orang dapat menerapkan transformasi linier untuk masalah pemrograman linier apa pun untuk membuat "tinggi" sesuai dengan jumlah yang akan dimaksimalkan), maka dari titik mana pun seseorang dapat melakukan perjalanan sepanjang sisi ke titik tertinggi tanpa harus pergi "menurun". Apa yang membuat pemrograman integer "sulit" adalah bahwa tidak ada ruang solusi kontinu, tetapi ada banyak ruang solusi terpisah , dan tidak ada cara untuk bekerja secara bertahap menuju solusi optimal.

supercat
sumber
2
Kata kunci di sini adalah "cembung"
cody
1
Bukankah bukit ini menaiki metode simpleks, yang tidak diketahui variannya polinomial dalam kasus terburuk?
jbapple
1
Ada banyak masalah yang lebih mudah diselesaikan di ruang diskrit (yang memungkinkan pencarian diskrit) daripada di ruang kontinu.
Raphael
@ Raphael: dapatkah Anda memberikan beberapa contoh masalah seperti itu? Saya sudah memikirkan hal ini dan tidak bisa menghasilkan banyak.
cody
@cody Mencari maxima / minima fungsi (satu dimensi), misalnya. Lihat di sini untuk contoh lucu yang hanya dapat menerima setelah mencatat bahwa kami dapat mengurangi ruang pencarian hingga menjadi terbatas. Perhatikan bahwa piringan hitam agak istimewa: dengan mencatat bahwa kita hanya perlu mempertimbangkan sudut polihedron, kita mendapatkan ruang pencarian yang terbatas. Secara umum, domain kontinu berarti tidak ada kekuatan kasar (dan tidak ada heuristik pintar untuk mempercepatnya).
Raphael
3

Jawaban lainnya benar, tetapi saya merasa sedikit teknis. Misalkan Anda telah menyapu (meniadakan) sebuah matriks dan mencari solusi apa pun dan matriksnya terlihat seperti ini:

column x1 x2 x3 x4 x5 x6 | solution
-----------------------------------
       1           1  1  | 3
          1              | 1
             1     1     | 2
                2  1  1  | 1

Dalam pemrograman lineair, sekarang Anda dapat mengatur kolom non-pivot (x5, x6) menjadi 0, dan mengatur x4 menjadi 0,5 dan menemukan solusi yang sepele. Dalam pemrograman integer, Anda tidak bisa hanya mengatur kolom non-pivot ke 0. Solusinya lebih sulit (NP-hard) untuk ditemukan. Perhatikan juga bahwa solusinya ada di , jadi ini tidak terkait langsung dengan presisi hingga / tak terbatas.Q

Albert Hendriks
sumber