Ah non. NP veux dire non-déterministique polynomial. Ce qui signifie l ́ensemble des problèmes soluble en un temps polynomial sur une machine d ́états non déterministique (Cela n ́existe pas en pratique. Mais les ordinateurs quantiques arrivent).
Donc il en pratique, il faut un temps plus que polynomial pour résoudre un problême appartenant à NP (et pas à P) Mais il existe des problèmes solubles en un temps exponentiel qui n ́appartiennent pas à NP.
[^] # Re: Mais ké kidi?
Posté par Gof (site web personnel) . En réponse au journal P != NP : la preuve. Évalué à 3.
Donc il en pratique, il faut un temps plus que polynomial pour résoudre un problême appartenant à NP (et pas à P) Mais il existe des problèmes solubles en un temps exponentiel qui n ́appartiennent pas à NP.