Masalah optimisasi "NP-complete"

Saya sedikit bingung dengan beberapa terminologi yang saya temui mengenai kompleksitas masalah optimasi. Dalam kelas algoritma, saya memiliki masalah kekikiran besar yang dijelaskan sebagai NP-lengkap. Namun, saya tidak yakin apa arti istilah NP-complete dalam konteks masalah optimisasi. Apakah ini hanya berarti bahwa masalah keputusan terkait adalah NP-complete? Dan apakah itu berarti bahwa masalah optimasi sebenarnya mungkin lebih sulit (mungkin di luar NP)?

Secara khusus, saya khawatir tentang fakta bahwa sementara masalah keputusan NP-lengkap dapat diverifikasi waktu polinomialnya, solusi untuk masalah optimisasi yang sesuai tampaknya tidak dapat diverifikasi waktu polinomialnya. Apakah itu berarti bahwa masalahnya tidak benar-benar dalam NP, atau apakah waktu polinom dapat diverifikasi hanya merupakan karakteristik dari masalah keputusan NP?

Upaya jawaban parsial:

Masalah keputusan sudah diselidiki untuk beberapa waktu sebelum masalah optimasi muncul, dalam arti karena mereka diperlakukan dari perspektif algoritma perkiraan.

Anda harus berhati-hati ketika membawa konsep dari masalah keputusan. Hal ini dapat dilakukan dan gagasan yang tepat tentang kelengkapan NP untuk masalah optimisasi dapat diberikan. Lihat jawaban ini . Ini tentu saja berbeda dari NP-kelengkapan untuk masalah keputusan, tetapi didasarkan pada ide yang sama (reduksi).

Jika Anda dihadapkan dengan masalah optimasi yang tidak memungkinkan verifikasi dengan solusi yang layak, maka tidak banyak yang dapat Anda lakukan. Itu sebabnya orang biasanya menganggap bahwa:

• Kami dapat memverifikasi secara efisien jika input tersebut adalah contoh yang valid dari masalah optimasi kami.
• Ukuran solusi yang layak dibatasi secara polinomi oleh ukuran input.
• Kami dapat memverifikasi secara efisien jika solusi merupakan solusi input yang layak.
• Nilai suatu solusi dapat ditentukan secara efisien.

Kalau tidak, tidak banyak yang bisa kita harapkan untuk dicapai.

$\mathrm{NP}$$\mathrm{NP}$$\mathrm{NP}$

Jika Anda ingin memverifikasi bahwa suatu solusi tidak hanya layak, tetapi juga optimal, saya akan mengatakan bahwa ini sama sulitnya dengan menyelesaikan masalah optimisasi awal karena, untuk menyangkal solusi yang layak dan mungkin optimal karena tidak optimal, Anda harus memberikan solusi yang lebih baik, yang mungkin mengharuskan Anda untuk menemukan solusi optimal yang sebenarnya.

Tetapi itu tidak berarti bahwa masalah optimasi lebih sulit. Lihat jawaban ini , yang tentu saja tergantung pada definisi yang tepat.

Alasan sebagian besar masalah pengoptimalan dapat digolongkan sebagai P, NP, NP-complete, dll., Adalah kondisi Kuhn-Tucker. Saya akan berbicara dalam hal masalah pemrograman linier, tetapi KTC berlaku dalam banyak masalah optimasi lainnya. Untuk setiap masalah optimasi ada dua. Jika tujuan dalam masalah asli adalah untuk memaksimalkan beberapa fungsi, maka dual (biasanya) memiliki fungsi yang harus diminimalkan. * Layak, tetapi solusi yang tidak optimal untuk masalah asli akan tidak layak / tidak valid untuk masalah ganda, dan sebaliknya -versa. Jika, dan hanya jika, solusi layak untuk primer dan ganda, itu adalah solusi optimal untuk keduanya. (Secara teknis, mungkin salah satu dari sejumlah besar solusi optimal yang memberikan hasil yang sama.)

Jadi menemukan solusi optimal dari masalah optimisasi sama dengan menemukan solusi yang valid untuk primer dan ganda. Anda dapat menggunakan algoritma pengoptimalan untuk menemukan solusi itu, tetapi proses keseluruhan adalah bukti keberadaan.

• Jika Anda ingin beralih dari minimalisasi ke maksimalisasi, kalikan fungsi objektif dengan -1.