Pourquoi prouver que la solution d'un problème est le temps polynomial est-il suffisant pour dire qu'il s'agit d'un NP prolbem? [dupliquer

Question

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

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

Pourquoi prouver que nous pouvons vérifier la solution d'un problème est le temps polynomial est suffisant pour dire que le problème est le temps polynomial non déterministe? Veuillez noter: ce n'est pas une question sur la façon de prouver qu'une question est NP, mais à la place, nous demandons pourquoi, nous pouvons simplement le faire? S'il y a plus d'étape que nous devons faire, que manque-t-il ici?

Je ne sais pas pourquoi prouver que nous pouvons vérifier que la solution d'un problème est le temps polynomial est suffisante pour dire que le problème en NP, car me semble que nous pouvons également vérifier une solution d'un problème est le temps polynomial alors qu'il est réellement linéaire temps, n'est-ce pas?

Prouver qu'un problème est en NP semble nécessiter une étape supplémentaire? c'est vraiment nécessaire?