Saya telah difasilitasi oleh ledakan luar biasa dalam Analisis Lancar dan dikejutkan oleh pernyataan di makalah Analisis Lancar dari Pemrograman Integer . Ini menyatakan bahwa Integer Linear Programming dalam Smoothed P jika Polynomially Bounded. Ini penting benar berdasarkan kebajikan bahwa Pemrograman Integer adalah Pseudo-polinomial!
Karena itu pertanyaannya adalah:
Apakah ini terbawa ke masalah lain secara universal? Khususnya apa saja kendalanya?
cc.complexity-theory
smoothed-analysis
Zelah 02
sumber
sumber
Jawaban:
Pemrograman integer sangat NP-keras, sehingga program integer secara umum tidak dapat diselesaikan dalam waktu semu-polinomial. Hasil Röglin dan Vöcking adalah bahwa, asalkan rentang bilangan bulat yang dapat diasumsikan variabel terikat secara polinomi, (acak) solvabilitas pseudo-polinomial setara dengan kompleksitas smoothing polinomial. Dengan demikian, program integer umum tidak memiliki kompleksitas polinomial smoothed.
Pernyataan "kompleksitas pseudo-polinomial acak = kompleksitas polinomial smoothed" tidak diketahui benar secara umum. Misalnya, heuristik balik untuk Max-Cut berjalan dalam waktu semu-polinomial, tetapi tidak diketahui apakah optimal lokal wrt heuristik dapat ditemukan dengan kompleksitas polinomial smoothed (lih. Etscheid dan Röglin, SODA 2014).
sumber