¿Cuáles son los “más duros” problemas utilizando el tiempo polinomio?

Question

Recientemente leí un trabajo de seminario que dice :

  

El algoritmo de coincidencia [para los gráficos generales] se puede extender   para el caso ponderada, que parece   ser uno de los combinatoria "más duro"   problemas de optimización que pueden ser   resuelto en tiempo polinómico.

inmediatamente la siguiente pregunta vino a la mente:

¿Conoce otros problemas "P-duro"?

Por ahora me gustaría definir P-duro como: "Un algoritmo polinomio se encontró muy tarde (después de 1950) en la literatura para ese problema" (O ¿cómo se podría definir mejor ". duro" si ya hay unos algoritmos deterministas que resuelve el problema en el tiempo polinomio?)

Answer 1

En realidad, hay problemas "P-completo", lo que significa que todos los demás problemas que se pueden calcular en tiempo polinómico puede reducirse a ellos. Ver http://en.wikipedia.org/wiki/P-complete .

Answer 2

Primes es en P .

Answer 3

Otro problema P "duro" es la solución de "programación lineal":

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Answer 4

Si usted quiere doblar un poco las reglas, a continuación, algoritmos de tiempo seudo-polinómica son los "más difícil" que pueda solucionar en "tiempo polinómico".

Un ejemplo clásico de un algoritmo de pseudo-polinomio es la solución de programación dinámica O(nW) a las href="http://en.wikipedia.org/wiki/Knapsack_problem" .

Answer 5

La Asignación problema que puede ser resuelto en O (n ³ ) por el modificado húngaro Algoritmo .