Apakah pemrograman linier menerima algoritma waktu polinomial yang kuat?

12

Masalah pemrograman linier: temukan algoritma waktu polinomial yang kuat yang untuk matriks A ∈ Rm × n dan b ∈ Rm menentukan apakah ada x ∈ Rn dengan Ax ≥ b.

Saya tahu bahwa Steve Smale's daftar beberapa masalah yang belum terpecahkan dalam matematika. Tetapi masalah pemrograman linier seperti itu sampai sekarang tidak dapat dipecahkan?

algorithms polynomial-time linear-programming Krebto
sumber
Masalah Pemrograman Linier tampaknya bisa diselesaikan dalam waktu polinomial menggunakan algoritma Simplex, itu hanya bukti yang hilang. Ditambah masalah yang mungkin ada contoh kontra, tetapi mereka tampaknya sangat sulit ditemukan.
gnasher729
2
@ gnasher729 Ada contoh tandingan yang diketahui, misalnya kubus Klee-Minty . Di sisi lain, ada algoritma titik interior yang diketahui dijalankan dalam waktu polinomial (lemah).
Tavian Barnes
Makalah ini terkait: cc.gatech.edu/~vempala/papers/affine.pdf
Erel Segal-Halevi

Jawaban:

12

Masalah ini masih terbuka. Lihat misalnya Wikipedia , yang walaupun bukan sumber yang dapat diandalkan secara umum, mungkin akan diperbarui jika algoritma waktu polinomial yang kuat pernah ditemukan.

Yuval Filmus
sumber