Quels sont les problèmes les plus difficiles « » en utilisant le temps polynomiale?

Question

J'ai lu récemment un travail séminaire qui dit :

  

L'algorithme de correspondance [pour les graphes généraux] peut être prolongée   le cas pondéré, qui semble   l'un des combinatoire « plus dur »   problèmes d'optimisation qui peuvent être   résolu en temps polynomial.

immédiatement la question suivante est venu à mon esprit:

Connaissez-vous d'autres problèmes "P-dur"?

Pour l'instant, je voudrais définir P-dur comme: « Un algorithme polynomiale a été trouvé très tardive (après 1950) dans la littérature pour ce problème » (Ou comment pourrait-on mieux définir ". dur »s'il y a déjà un algorithme déterministe qui permet de résoudre le problème en temps polynomial?)

Answer 1

Il y a effectivement des problèmes « P-complet », ce qui signifie que tous les autres problèmes qui peuvent être calculées en temps polynomial peut être réduit à eux. Voir http://en.wikipedia.org/wiki/P-complete .

Answer 2

nombres premiers est en P .

Answer 3

Un autre "dur" problème P est la résolution "programmation linéaire":

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

Answer 4

Si vous voulez plier les règles un peu, puis algorithmes pseudo-polynomial sont les « plus dur » que vous pouvez résoudre en « temps polynomiale ».

Un exemple classique d'un algorithme pseudo-polynôme est la solution de programmation dynamique O(nW) aux havresac .

Answer 5

Le problème Affectation qui peut être résolu en O (n ³ ) par la modification algorithme hongrois .