¿La programación lineal admite un algoritmo de tiempo fuertemente polinómico?

12

El problema de la programación lineal: encuentre un algoritmo de tiempo fuertemente polinomial que para la matriz dada A ∈ Rm × ny b ∈ Rm decida si existe x ∈ Rn con Ax ≥ b.

Sé que Steve Smale enumera algunos de los problemas no resueltos en matemáticas. Pero tal problema de programación lineal es hasta ahora no solucionable?

Krebto
fuente
Los problemas de programación lineal parecen resolverse en tiempo polinómico usando el algoritmo Simplex, es solo la prueba que falta. Además, el problema es que puede haber ejemplos contrarios, pero parecen muy difíciles de encontrar.
gnasher729
2
@ gnasher729 Hay contraejemplos conocidos, por ejemplo, el cubo Klee-Minty . Por otro lado, hay algoritmos de punto interior que se sabe que se ejecutan en tiempo polinomial (débilmente).
Tavian Barnes
Este documento está relacionado: cc.gatech.edu/~vempala/papers/affine.pdf
Erel Segal-Halevi

Respuestas:

12

Este problema aún está abierto. Consulte, por ejemplo , Wikipedia , que aunque no es una fuente confiable en general, probablemente se actualizará si alguna vez se encuentra un algoritmo de tiempo fuertemente polinómico.

Yuval Filmus
fuente