Qu'est-ce qui manque pour cette preuve p! = Np?

Question

J'ai essayé de récupérer un mot de passe. En y réfléchissant, j'ai reconnu que le problème de «récupération de mot de passe» est un très bel exemple de problème NP. Si vous connaissez le mot de passe, il est très facile de le vérifier en temps polynomial. Mais si vous ne connaissez pas le mot de passe, vous devez rechercher tout l'espace des solutions possibles qui peuvent être montrées pour prendre du temps exponentiel.

Maintenant, ma question est: cela ne démontre-t-il pas que P! = NP Puisque la "récupération de mot de passe" est un élément de NP qui peut être démontré qu'il faut plus que du temps polynomial pour fonctionner?

Answer 1

Le problème ne montre pas que la récupération de mot de passe est non polynomiale, car il est clairement - vous devez rechercher un espace exponentiel de réponses.

En fait, "la récupération de mot de passe" n'est pas vraiment une description d'une norme problème de calcul. Il semble que, formellement, les algorithmes de rupture de mot de passe prennent une sorte d'oracle qui peut répondre si une chaîne donnée est le mot de passe correct. Cependant, P et NP sont définis en termes de machines Turing, qui prennent des chaînes en entrée.

Answer 2

Si vous montrez cela n'importe quel L'algorithme qui résout la «récupération du mot de passe» nécessite plus que le temps polynomial, puis il démontre que p ≠ np.

Sinon, si vous ne montrez que Une solution particulière nécessite plus que du temps polynomial, il ne montre rien. Je peux écrire un type pour nécessiter un temps exponentiel (mélange de licenciements jusqu'à ce qu'il soit trié), mais cela ne signifie pas qu'il n'y a pas de solution polynomiale.

Answer 3

NP ne signifie pas «non-polynomial», si c'est ce que vous pensiez (et mes excuses à l'avance si vous ne l'étais pas!). Cela signifie "polynôme non déterministe". Un algorithme non déterministe est celui qui équivaut à un nombre illimité d'instances parallèles d'un algorithme. Par exemple, trouver le mot de passe correct par force brute est le polynôme non déterministe: si vous imaginez que la vérification du mot de passe, si votre supposition est correcte, prend du temps linéaire (c'est-à-dire polynôme) sur la longueur du mot de passe, mais que vous devez Vérifiez un nombre arbitraire de mots de passe possibles (k ^ n) en parallèle, puis le coût de la recherche de la solution à l'aide de cette méthode est le polynôme non déterministe.

Un algorithme non déterministe peut également être pensé à celui dont l'État se ramifie à certaines étapes. Un exemple simple de ceci est un automate fini non déterministe (NFA) - parfois vous ne savez pas quel bord prendre entre les États, vous les prenez donc tous les deux. Il est facile de montrer que chaque NFA équivaut à une FA déterministe, et il est donc alléchant de penser que la même chose pourrait être prouvée pour d'autres classes d'algorithmes intéressantes. Malheureusement, il est difficile de le faire pour le cas général de l'algorithme polynomial, et le suspicion général est qu'ils ne sont pas équivalents, c'est-à-dire que P! = Np.

Answer 4

Le raisonnement que le problème est en NP est correct: s'il peut être vérifié en temps polynomial, c'est en NP. Même des problèmes très simples sont en NP. Fondamentalement, tout P est inclus dans NP. (*)

Maintenant, voici une façon pour que vous puissiez transformer cela en une preuve que p! = Np:

1) Montrer que la «récupération de mot de passe» est complete NP. Autrement dit, tout problème dans NP peut être réduit à la «récupération du mot de passe» en temps polynomial. (c'est-à-dire qu'il existe un algorithme efficace pour convertir tout autre problème NP en "Récupération de mot de passe".)

2) Une fois que vous en avez alors, comme Pavel Shved mentionne, il ne suffit pas de montrer que l'algorithme intuitif est non polynomial. Vous devez montrer qu'il n'existe pas d'algorithme polynomial pour résoudre la "récupération du mot de passe". Une tâche très difficile.

(*) Edmund est également correct: NP signifie polynôme sur une machine non déterministe. Une vérification polynomiale est essentiellement le chemin choisi par la machine non déterministe.

Answer 5

1. Comme indiqué, la «récupération du mot de passe» n'est pas un problème de décision.
2. Vous n'avez pas prouvé que la "récupération de mot de passe" n'a pas d'algorithme de temps polynomial, vous avez simplement fait valoir pour des motifs intuitifs qu'il ne le fait pas. Ce n'est pas parce qu'un espace de solution est gigantesque qu'il n'y a pas d'algorithmes rapides pour trouver la solution; Par exemple, il y a n! permutations d'un ensemble de n entiers distincts mais un seul est trié montant, mais nous pouvons le trouver dans n log n temps. Pour un exemple plus amusant, voir Projet Euler # 67.
3. Même si vous avez reformulé la "récupération du mot de passe" comme problème de décision et que vous avez pu montrer qu'il n'y a pas d'algorithme de temps polynomial pour le résoudre, vous devez maintenant prouver que la "récupération du mot de passe" est-complé.

Pour plus de détails sur P / NP / etc. regarde ça question précédente.

Answer 6

L'énoncé officiel de ce problème serait celui qui accepterait comme entrée la valeur hachée (et le sel) et tente de trouver un Mot de passe qui générera ce hash: votre problème de recherche de collision CypherText connu de base.

Selon la qualité du hachage, ce pourrait ne pas nécessitent du temps exponentiel. En effet, de nombreux hachés cryptographiques dans une utilisation généralisée ont identifié des attaques qui fonctionnent plus rapidement que les recherches sur les espaces.

Ce qui veut dire: vous (et certains des autres répondants) assumé que la routine de muniging de mot de passe a toutes les propriétés que les concepteurs voulaient qu'elles aient. Cela devrait être prouvé.

Answer 7

Écrire cette réponse parce que j'avais cette idée à un moment donné, et les réponses ici n'étaient pas satisfaisantes.

Vous avez prouvé que p = / = np sous la présence d'un «oracle» (c'est la chose qui indique si le mot de passe est correct ou non).

Il a été démontré que vous ne pouvez pas prouver le P vs NP d'origine en utilisant des oracles (cette technique est appelée relativisation).

Afin de prouver le problème d'origine, vous devez définir l'Oracle en termes de machine Turing. En d'autres termes, vous devez décrire ce que fait le vérificateur de mot de passe avec l'entrée, puis prouver qu'il n'y a pas d'algorithme qui peut deviner le mot de passe étant donné le code du vérificateur de mot de passe.

Notez que vous devez le faire pour un éventuel vérificateur de mot de passe rapide. La seule exigence de l'algorithme de vérificateur de mot de passe est qu'il s'exécute en temps polinomial en ce qui concerne la durée du mot de passe.

Ainsi, étant donné tout algorithme possible qui vérifie si le mot de passe est correct ou non en temps polinomial, vous devez écrire un algorithme qui lit l'algorithme du vérificateur et essaie de deviner que le mot de passe est en temps polis. Si vous pouvez prouver ou réfuter qu'un tel algorithme existe, vous avez résolu le problème.