Apakah semua masalah Program Integer Linear NP-Hard?

Seperti yang saya mengerti, masalah penugasan dalam P karena algoritma Hungaria dapat menyelesaikannya dalam waktu polinomial - O (n ³ ). Saya juga mengerti bahwa masalah penugasan adalah masalah pemrograman linear integer , tetapi halaman Wikipedia menyatakan bahwa ini adalah NP-Hard. Bagi saya, ini menyiratkan masalah penugasan dalam NP-Hard.

Tapi tentunya masalah penugasan tidak bisa di P dan NP-Hard, kalau tidak P akan sama dengan NP? Apakah halaman Wikipedia hanya berarti bahwa algoritma umum untuk menyelesaikan semua masalah ILP adalah NP-Hard? Beberapa sumber lain menyatakan bahwa ILP adalah NP-Hard jadi ini benar-benar membingungkan pemahaman saya tentang kelas kompleksitas secara umum.

Jika masalah adalah NP-Hard itu berarti ada kelas contoh masalah yang NP-Hard. Sangat memungkinkan bagi kelas instance spesifik lainnya untuk dipecahkan dalam waktu polinomial.

Pertimbangkan misalnya masalah menemukan 3-warna grafik . Ini adalah masalah NP-Hard yang terkenal. Sekarang bayangkan contohnya dibatasi untuk grafik yang, misalnya, pohon. Jelas Anda dapat dengan mudah menemukan 3 warna pohon dalam waktu polinomial (memang Anda juga dapat menemukan 2 warna).

Pertimbangkan masalah keputusan sesaat. Metode untuk membuktikan kekerasan dari masalah keputusan adalah merancang pengurangan polinomial (Karp) dari masalah lain yang dikenal sebagai NP-Hard. Dalam pengurangan ini Anda menunjukkan bahwa ada fungsi yang memetakan setiap contoh masalah ke sebuah contoh dari masalah sehingga: adalah contoh ya untuk adalah contoh ya untuk . Ini menyiratkan bahwa penyelesaian harus "setidaknya sama sulitnya" dengan penyelesaian itu sendiri.Q f q Q P q $P$$Q$$f$$q$$Q$$P$$q$P f ( q ) $Q \iff f(q)$$P$$f(q)$$q$

Perhatikan bagaimana hal itu tidak diperlukan untuk citra untuk menjadi sama dengan himpunan contoh dari . Oleh karena itu sangat mungkin untuk masalah terbatas pada beberapa bagian contoh untuk tidak sulit.P $f$$P$$P$

Untuk kembali ke pertanyaan awal Anda:

• Masalah penugasan dapat diselesaikan dalam waktu polinomial, yaitu solusi untuk setiap contoh masalah penugasan dapat dihitung dalam waktu polinomial.
• ILP adalah NP-Hard: secara umum mungkin sulit untuk menghitung solusi untuk masalah ILP, yaitu ada beberapa contoh ILP yang sulit.
• Beberapa contoh ILP spesifik dapat diselesaikan dalam waktu polinomial.

Tidak, kasing khusus bisa lebih mudah.

Pertimbangkan IP ini, misalnya, diberi untuk :$a_i \geq 0$$i \in [1..n]$

$\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$

st dan untuk .$\quad\displaystyle\sum_{i=1}^n x_i \geq 1$
$\ \displaystyle x_i \in \mathbb{N}$$i \in [1..n]$

Ia menemukan minimum di antara (untuk yang mana, pasti, dalam solusi optimal). Menemukan minium nomor jelas merupakan masalah polinomial.$a_1, \dots, a_n$$x_i=1$$n$

Anda dapat memodelkan masalah yang dapat diselesaikan secara polinomi sebagai IP. Ini tidak berarti masalahnya adalah NP-hard. Ini berarti bahwa tidak ada algoritma polinomial yang diketahui untuk menyelesaikan model IP masalah Anda (kecuali P = NP).

Jadi seperti yang Anda sarankan, masalah penugasan dalam P tetapi model IP Anda itu NP-hard.

Tidak, ada jenis khusus dari program integer, jika matriks kendala adalah TUM (matriks benar-benar unimodular), maka dapat dilonggarkan ke dalam program linier, yang dapat diselesaikan dalam waktu polinomial.

Masalah penugasan bukan ILP, tetapi masalah LP dan karenanya bukan NP-hard.