10
poco leí a seminar work que dice:¿Cuáles son los problemas "más difíciles" con el uso de tiempo polinomial?
El algoritmo de coincidencia [para los gráficos generales] se puede extender al caso ponderada, que parece ser uno de los "más duros" problemas de optimización combinatoria que pueden ser resuelto en tiempo polinomial.
inmediatamente la siguiente pregunta vino a mi mente:
¿Conoce a otros problemas "P-duro"?
Por ahora me gustaría definir P-hard como: "Un algoritmo polinomial se encontró muy tarde (después de 1950) en la literatura para ese problema". (¿O cómo podría uno definir mejor "hard" si ya hay un algoritmo determinístico que resuelve el problema en tiempo polinomial?)
Me gustaría pedir problemas con un límite inferior alto en P. – ebo
En mi humilde opinión, un límite no puede y no debe ser comparado * a través de * diferentes tipos de algoritmos o ¿qué quiere decir con un límite inferior? – Karussell
Probablemente cierto, pero tampoco es una pregunta muy científica ;-) Límite inferior: el problema tiene un límite inferior de Omega (n ** x). – ebo