A programação linear admite um algoritmo de tempo fortemente polinomial?

12

O problema de programação linear: encontre um algoritmo de tempo fortemente polinomial que para a matriz A ∈ Rm × n eb ∈ Rm decida se existe x ∈ Rn com Ax ≥ b.

Eu sei que o de Steve Smale lista alguns dos problemas não resolvidos em matemática. Mas esse problema de programação linear é até agora insolúvel?

algorithms polynomial-time linear-programming Krebto
fonte
Problemas de programação linear parecem ser resolvidos em tempo polinomial usando o algoritmo Simplex, é apenas a prova que está faltando. Além do problema que pode haver exemplos contrários, mas eles parecem muito difíceis de encontrar.
precisa saber é o seguinte
2
@ gnasher729 Existem contra-exemplos conhecidos, por exemplo, o cubo Klee-Minty . Por outro lado, existem algoritmos de pontos interiores conhecidos por serem executados em tempo polinomial (fracamente).
Tavian Barnes
Este artigo está relacionado: cc.gatech.edu/~vempala/papers/affine.pdf
Segal-Halevi

Respostas:

12

Esse problema ainda está aberto. Veja, por exemplo , a Wikipedia , que embora não seja uma fonte confiável em geral, provavelmente será atualizada se um algoritmo de tempo fortemente polinomial for encontrado.

Yuval Filmus
fonte