La relation exacte entre les classes de complexité et de la complexité de l'algorithme [double]

Question

Cette question a déjà une réponse ici:

• Quelle est la définition de P, NP, NP -complete et NP-dur? 7 réponses

sont tous les algorithmes qui ont la complexité polynomiale appartiennent à la classe P? Et la classe P ne possède pas l'algorithme qui ne possède pas la complexité polynomiale?

sont tous les algorithmes qui ont la complexité non polynomiale appartiennent à NP ou NP-dur ou les deux?

Je suis juste essayer de comprendre la relation de base.

Answer 1

$ P $ est définie comme la classe (décision) des problèmes qui ont un algorithme qui les résout en temps polynomial (dans un TM ou un modèle équivalent) polynomiale-. Ainsi, $ P $ contient exactement ces problèmes, ni plus ni moins.

Quant à $ NP $ - la situation est plus délicate. Un problème est en $ NP $ si elle a un algorithme non déterministe qui fonctionne en temps polynomiale. Une définition équivalente, plus convivial, est une solution que, compte tenu du problème, vous pouvez vérifier son exactitude en temps polynomial dans la taille du problème. Par exemple, étant donné un graphe et un chemin qui prétend être un hamiltonien, vous pouvez vérifier en temps polynomial qu'il est en effet un chemin hamiltonien. Ainsi, le problème de décider si un graphe a un chemin hamiltonien est en $ NP $.

Précision: $ NP $ est une classe de problèmes , pas de algorithmes . Un algorithme ne appartiennent à $ NP $.

Maintenant, certains problèmes sont connus de ne pas avoir un algorithme polynomial. Cela ne signifie pas qu'ils sont en $ NP $. En fait, certains problèmes sont connus pour ne pas être en $ NP $. Par exemple, tout NEXP $ $ problème -hard.

En ce qui concerne $ NP $ problèmes -Hard - puisque nous ne savons pas si $ P = NP $ ou non, nous ne savons pas si tous les problèmes en dehors $ P $ est $ NP -hard $. Si $ NP = P $, alors chaque problème est $ NP $ -Hard (sauf $ \ Sigma ^ * $ et $ \ emptyset $).

Cette réponse (qui est de loin incomplète) couvre environ 3 semaines de matériel en cours de complexité de base. Peut-être envisager un manuel de lecture à fond, comme « théorie de calcul » de Sipser.

Answer 2

Tous les algorithmes qui permettent de résoudre un problème de décision montrent polynomiale que leurs problèmes sont en $ $ P. Mais il y a certainement des algorithmes qui ne prennent pas le temps polynomiale pour des problèmes de $ P $. Vous pourriez sorte en générant tout n $! $ Permutations de l'entrée, et vérifiez chaque si elle est triée. Cet algorithme ne prend que le temps une plus exponentielle, mais le problème a une solution en temps polynomial.