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?
Respuestas:
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.
fuente