• [^] # Re: d'un autre coté ...

    Posté par . En réponse au journal La NSA et la vie privée. Évalué à 1.

    heu ...

    j'essaie de relire ce que j'ai écrit, cela dit :

    un probleme NP-complet ne peut pas etre résolu en un temps polynomiale sur une machine de turing deterministe ...



    que vient faire prix Clay là dedans ?

    parce qu'apres la meme page :
    De manière intuitive, dire qu'un problème peut être décidé à l'aide d'un algorithme non-déterministe polynomial signifie qu'il est facile, pour une solution donnée, de vérifier en un temps polynomial si celle-ci répond au problème pour une instance donnée (à l'aide d'un Certificat); mais que le nombre de solutions à tester pour résoudre le problème est exponentiel par rapport à la taille de l'instance. Le non-déterminisme permet de masquer la taille exponentielle des solutions à tester tout en permettant à l'algorithme de rester polynomial.