En gros : P, c'est l'ensemble des problèmes que l'on peut résoudre en temps polynômial (i.e. dont le temps de résolution est majoré par une fonction polynômiale de la taille des paramètres), et NP ceux que l'on peut résoudre en temps exponentiel (exemple : à partir d'une expression logique à N variables, trouver des valeurs de vérité qui satisfont l'expression).
Pour être un peu plus précis, les problèmes NP sont des problèmes qui peuvent être résolus en temps polynomial avec une machine non-déterministe.
Ça veut dire que le problème peut être compliqué a résoudre avec une machine déterministe (factoriser un grand nombre n par exemple), mais que une fois qu'on a trouvé la solution, on peut vérifier en temps polynomial que la solution est correcte (vérifier que p.q = n par exemple).
[^] # Re: Mais ké kidi?
Posté par François Trahay . En réponse au journal P != NP : la preuve. Évalué à 6.
En gros : P, c'est l'ensemble des problèmes que l'on peut résoudre en temps polynômial (i.e. dont le temps de résolution est majoré par une fonction polynômiale de la taille des paramètres), et NP ceux que l'on peut résoudre en temps exponentiel (exemple : à partir d'une expression logique à N variables, trouver des valeurs de vérité qui satisfont l'expression).
Pour être un peu plus précis, les problèmes NP sont des problèmes qui peuvent être résolus en temps polynomial avec une machine non-déterministe.
Ça veut dire que le problème peut être compliqué a résoudre avec une machine déterministe (factoriser un grand nombre n par exemple), mais que une fois qu'on a trouvé la solution, on peut vérifier en temps polynomial que la solution est correcte (vérifier que p.q = n par exemple).