Estoy interpretando su pregunta como preguntando si algún algoritmo de programación lineal tiene una complejidad de tiempo polinómica. Una búsqueda en google para:
complejidad de programación lineal
Aparece casi 2 millones de visitas. Al echar un vistazo a ese material, queda claro que la solución más popular para los problemas de programación lineal, el método Simplex no es de complejidad de tiempo polinomial, pero sí lo son los métodos elipsoides, particularmente el algoritmo de Karmakar. Ver: página en stanford.edu
- ¿Cuáles son las aplicaciones más prácticas (vida cotidiana) del algoritmo de agrupación de k-means? ¿Cómo se ha utilizado exactamente k-means en estas aplicaciones?
- ¿Cuáles son algunas aplicaciones prácticas de los árboles AVL y los árboles de separación?
- ¿Qué método se ejecuta más rápido para una matriz con todas las claves idénticas, tipo burbuja o tipo inserción?
- ¿Es importante memorizar algoritmos?
- ¿Qué es el algoritmo de YouTube?
El análisis de la complejidad de las soluciones a los problemas de programación lineal no es fácil. Es desconcertante que, en teoría, el algoritmo de Karmakar sea mejor, pero en la práctica, el algoritmo Simplex generalmente gana.
En respuesta al comentario de que descuidé el calificador “fuerte” en su pregunta sobre la complejidad del tiempo polinómico, aquí hay otro enlace: Página en gatech.edu
