J'ai deux problèmes.Frontière de dureté NP
Y at-il une clique de taille k dans un graphique? NP Hard
Existe-t-il une clique de taille 50 dans un graphique? - Peut être trouvé en O polynomiale (n^50)
Pourquoi le deuxième problème ne NP dur alors que le premier est?
EDIT: En supposant P = NP
Le premier problème est NP-difficile car un problème arbitraire NP-complet (par exemple, 3-SAT) peut y être réduit en temps polynomial. (par la définition de NP-dureté)
Le deuxième problème n'est pas NP-difficile, parce qu'un problème NP-complet arbitraire ne peut pas être réduit à lui (disons, 3-SAT, avec> 50 clauses).
En fait, le deuxième problème est en P, parce que O(n^50) appartient à P. Mais ce n'est pas la raison pour laquelle il est NP-dur (en particulier, NP ne signifie non polynomiale).
n^k est exponentielle alors que n^50 est polynomiale.
Il peut très bien être NP dur (si P = NP). – Henrik
question cstheory? Et n'utilisez pas de bloc de code pour un devis - il devient difficile à lire;). En ce qui concerne la question elle-même, je pense que c'est parce que 50 est une constante, où k ne l'est pas, donc nous ne pouvons pas réduire les limites. – Robert