Résolution de P=NP

2»

Réponses

  • @octobre Si tu veux comprendre la définition classique des classes de complexité, il faut d'abord que tu comprenne ce qu'est une machine de Turing. Pour l'instant, tu montres surtout que tu n'as rien compris. Si tu savais ce qu'est une machine de Turing, tu te rendrais compte de l'absurdité de tes remarques.
  • octobre
    Modifié (12 Jun)
    Bibix 
    Vous pouvez m'expliquer un peu plus surtout on trouve beaucoups de question dans internet qui sont en lien avec la machine de Turing genre  en utilisant le chiffre 4 exactement quatre fois, et 4 signes exactement et seule l'opération + est autorisée comment obtenir 10?
    Cette question est impossible mathématiquement mais il a bien 3 réponses informatique  :D
  • Le problème de décision associé à la factorisation est clairement $NP$ (on devine le facteur et on vérifie qu'il convient) et est également dans $BQP$ par l'algorithme de Shor. Toutefois, le problème de factorisation n'étant a priori pas $NP$-dur, cela ne prouve aucunement $NP = BQP$. On ne peut donc déduire de cela $P = BQP \Rightarrow NP = BQP$. Pour prouver que $NP = BQP$, il faudrait réussir à trouver un algo polynomial quantique pour un problème $NP$-dur comme $SAT$, la factorisation n'étant pas a priori un problème $NP$-dur.
Connectez-vous ou Inscrivez-vous pour répondre.