J'ai essayé de récupérer un mot de passe. En pensant à cela, j'ai reconnu que le problème «récupération du 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 pouvant être montrées pour prendre du temps exponentiel.
Maintenant ma question est la suivante: ne démontre-t-elle pas que p! = np depuis "la récupération du mot de passe" est un élément de NP qui peut être démontré que le temps de polynomial doit être exécuté?
7 Réponses :
Si vous montrez que tout algorithme qui résout "récupération du mot de passe" nécessite plus que du temps polynôme, 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 démontre rien. Je peux écrire une sorte pour nécessiter une heure exponentielle (matrice de shuffle jusqu'à ce qu'elle soit triée), mais cela ne signifie pas qu'il n'y a pas de solution polynomiale.
Non, vous devez également reformuler la "récupération du mot de passe" comme un problème de décision et montrer que le problème reproché est NP-complet.
Mais comment savoir autranger le problème de la fissuration d'un mot de passe arbitraire résolu comme par une force brute qui nécessite une période exponentielle? N'est-ce pas le cœur du problème que la solution (par exemple le mot de passe) doit être connue sinon vous devriez rechercher l'espace complet de la solution?
@gruenewa: L'objectif est de le rendre dur (c'est-à-dire de faire du cryptage de mot de passe Facile et du déchiffrement dur). Mais la preuve que votre algorithme se comporte de cette manière (comme dans: le décryptage ne peut pas être calculé en temps polynomial sur une machine déterministe) n'a jamais été faite.
NP ne signifie pas "non polynomial", si c'est ce que vous pensais (et mes excuses d'avance si vous n'étiez pas!). Cela signifie "polynôme non déterministe". Un algorithme non déterministe est un algorithme qui est équivalent à un nombre non lié d'instances parallèles d'un algorithme. À titre d'exemple, la recherche du mot de passe correct par la force brute est un polynôme non déterministe: si vous imaginez que la vérification du mot de passe, si votre hypothèse est correcte, prend du temps linéaire (c'est-à-dire polynomial) sur la longueur du mot de passe, mais que vous devez avoir besoin de 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 un polynôme nondéterministe.
Un algorithme non déterministe peut également être considéré comme celui dont les branches d'État à quelques é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, de sorte que vous les preniez tous les deux. Il est facile de montrer que chaque NFA est équivalente à une FA déterministe, et il est donc grave de penser que la même chose pourrait être prouvée pour d'autres classes d'algorithme intéressantes. Malheureusement, il est difficile de le faire pour le cas général d'algorithme polynomial, et la suspicion générale est qu'elles ne sont pas équivalentes, c'est-à-dire que p! = NP.
Le raisonnement que le problème est dans NP est correct: s'il peut être vérifié en temps polynomial, il est en np. Même des problèmes très simples sont dans NP. Fondamentalement, tous p sont inclus dans NP. (*)
Maintenant, voici une façon dont vous pourriez aller à la transformer en une preuve que p! = NP:
1) montre que "la récupération du mot de passe" est NP-complète. C'est-à-dire que tout problème dans NP peut être réduit à la "récupération du mot de passe" en temps polynomial. (C'est-à-dire un algorithme efficace pour convertir tout autre problème NP en "récupération de mot de passe".)
2) Une fois que vous aurez cela, alors que Pavel Shoped 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 juste: 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.
Jason Commentaire sur la «récupération du mot de passe» ne pas être un problème de décision est juste. Cependant, dans la pratique, ce n'est souvent pas un problème, car il existe des "astuces" pratiques pour transformer des problèmes de décision de / en problèmes de réponse libre. Par exemple, au lieu de "récupération du mot de passe", vous pouvez demander au système: "est le mot de passe ci-dessus mmmmmmmmm ou ci-dessous?".
Vous n'avez pas à montrer que c'est NP-complet. Il suffit de prouver une liaison inférieure de la complexité de tout problème dans NP, pas seulement des complètes, de séparer les deux classes et de montrer que p! = NP.
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, "mot de passe-récupération" n'est pas vraiment une description d'une standard Problème de calcul . Il semble que, formellement, des algorithmes de casse de mot de passe prennent une sorte de "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 de Turing, qui prennent des chaînes comme entrée.
La récupération de mot de passe de la force brute est de tous les moyens d'un problème de calcul. Il est facilement réductible à une entrée valide dans la machine Turning Standard. De telles réductions constituent une base substantielle de l'ensemble des sciences informatiques.
n! permutations d'un ensemble d'entiers N , mais un seul est trié monument ascendant, nous pouvons le trouver dans n log n temps. Pour un exemple plus amusant, voir Project Euler # 67 .
- Même si vous avez repassé "la récupération du mot de passe" comme un problème de décision et que vous avez pu montrer qu'il n'y a pas un algorithme de temps polynomial pour la résolution, vous devez maintenant prouver que "la récupération du mot de passe" est NP-complète. < / li>
Pour plus de détails sur p / np / etc. Voir cette Question précédente .
La déclaration formelle de ce problème serait celle qui accepte comme entrée la valeur hachée (et le sel) et tente de trouver un mot de passe qui générera ce hachage: votre problème de collision CYPHertext connu de base.
Selon la qualité du hachage, ce pourrait ne pas nécessiter une heure exponentielle. En effet, de nombreux hachés cryptographiques utilisés dans une utilisation généralisée ont identifié des attaques qui fonctionnent plus rapidement que les recherches de Keyspace.
qui est à dire: vous (ans certains des autres intervenants) ont supposé que la routine muning de mot de passe a toutes les propriétés que les concepteurs souhaitaient avoir. Cela devrait être prouvé .
É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 juste ou non).
Il a été montré que vous pouvez réellement ne pas prouver l'original P vs NP 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 d'une machine de Turing. En d'autres termes, vous devez décrire le vérificateur de mot de passe avec l'entrée, puis prouve qu'il n'y a pas d'algorithme pouvant deviner le mot de passe étant donné le code de vérificateur de mot de passe.
Notez que vous devez le faire pour tout vérificateur de mot de passe rapide possible. La seule exigence de l'algorithme de vérificateur de mot de passe est qu'elle fonctionne en temps polinomial en ce qui concerne la longueur du mot de passe.
Ainsi, étant donné n'importe quel algorithme éventuel qui vérifie si le mot de passe est correct ou non en temps polinomial, vous devez écrire un algorithme qui lit l'algorithme de vérificateur et tente de deviner le mot de passe est en temps polinomial. Si vous pouvez prouver ou réfuter que cet algorithme existe, vous avez résolu le problème.
J'ai découvert une preuve vraiment remarquable que cette marge est trop petite pour contenir