Was fehlt für diesen P! = NP -Beweis?

Question

Ich habe versucht, ein Passwort wiederherzustellen. Wenn ich darüber nachdachte, erkannte ich, dass das Problem "Passwortwiederherstellung" ein sehr schönes Beispiel für ein NP -Problem ist. Wenn Sie das Passwort kennen, ist es sehr einfach, es in Polynomzeit zu überprüfen. Wenn Sie jedoch das Passwort nicht kennen, müssen Sie den gesamten Speicherplatz möglicher Lösungen durchsuchen, die gezeigt werden können, dass sie exponentielle Zeit benötigen.

Jetzt ist meine Frage: Zeigt dies nicht, dass P! = NP, da "Passwortwiederherstellung" ein Element von NP ist, das nachgewiesen werden kann, dass sie mehr als Polynomzeit zum Laufen benötigen?

Answer 1

Das Problem ist nicht, dass die Wiederherstellung der Kennwortwiedergabe nicht polynomisch ist, da es eindeutig ist-Sie müssen einen exponentiellen Antwortenraum durchsuchen.

Tatsächlich ist "Passwort-Recovery" nicht wirklich eine Beschreibung eines Standards Rechenproblem. Es scheint, dass offiziell Passwort -Brechungsalgorithmen eine Art "Orakel" einnehmen können, die beantworten können, ob eine bestimmte Zeichenfolge das richtige Passwort ist. P und NP werden jedoch in Bezug auf Turing -Maschinen definiert, die Zeichenfolgen als Eingabe dauern.

Answer 2

Wenn Sie das zeigen irgendein Der Algorithmus, der "Kennwortwiederherstellung" löst, erfordert mehr als Polynomzeit, dann zeigt er, dass P ≠ NP.

Andernfalls, wenn Sie das nur zeigen eine bestimmte Lösung erfordert mehr als Polynomzeit, es zeigt nichts. Ich kann eine Sortierung schreiben, um eine exponentielle Zeit zu benötigen (Shuffle -Array, bis sie sortiert ist), aber das bedeutet nicht, dass es keine Polynomlösung gibt.

Answer 3

NP bedeutet nicht "unpolynomisch", wenn Sie das gedacht haben (und ich entschuldige mich im Voraus, wenn Sie es nicht waren!). Es bedeutet "nicht deterministisches Polynom". Ein nichtdeterministischer Algorithmus entspricht einer unbegrenzten Anzahl paralleler Instanzen eines Algorithmus. Beispielsweise ist das Finden des richtigen Passworts durch Brute -Kraft nicht deterministisches Polynom: Wenn Sie sich vorstellen, dass das Passwort das Überprüfen des Passworts ist, nimmt Sie die lineare (dh polynomiale) Zeit für die Länge des Passwort Überprüfen Sie eine willkürliche Anzahl möglicher Kennwörter (K^n) parallel, und die Kosten für die Suche nach der Lösung mit dieser Methode sind nicht deterministisches Polynom.

Ein nichtdeterministischer Algorithmus kann auch an einen gedacht werden, dessen Staatsstaatsanwalt sich in einigen Schritten verzweigt. Ein einfaches Beispiel hierfür ist ein nichtdeterministischer endlicher Automaton (NFA) - manchmal wissen Sie nicht, welche Kante zwischen den Staaten eingehen soll, also nehmen Sie sie beide. Es ist leicht zu zeigen, dass jede NFA einem deterministischen FA entspricht, und es ist verlockend zu glauben, dasselbe für andere interessante Algorithmusklassen bewiesen werden kann. Leider ist es für den allgemeinen Fall des Polynomalgorithmus schwierig, und der allgemeine Verdacht ist, dass sie nicht gleichwertig sind, dh p! = Np.

Answer 4

Die Argumentation, dass das Problem in NP ist, ist korrekt: Wenn es in der Polynomzeit überprüft werden kann, ist es in NP. Selbst sehr einfache Probleme sind in NP. Grundsätzlich ist alles P in NP enthalten. (*)

Hier ist eine Möglichkeit, dies in einen Beweis zu verwandeln, den P! = NP:

1) Zeigen Sie, dass die "Passwortwiederherstellung" NP-Vervollständigung ist. Das Problem in NP kann in der Polynomzeit auf "Kennwortwiederherstellung" reduziert werden. (IE Es gibt einen effizienten Algorithmus, um ein anderes NP -Problem in "Passwortwiederherstellung" umzuwandeln.)

2) Sobald Sie dies dann haben, wie Pavel Shved erwähnt, reicht es nicht aus, um zu zeigen, dass der intuitive Algorithmus nicht polynomisch ist. Sie müssen zeigen, dass kein Polynomalgorithmus vorhanden ist, um "Passwortwiederherstellung" zu lösen. Eine sehr schwierige Aufgabe.

(*) Edmund ist auch richtig: NP bedeutet Polynom auf einer nicht deterministischen Maschine. Eine Polynomüberprüfung ist im Wesentlichen der von der nicht deterministische Maschine ausgewählte Pfad.

Answer 5

1. Wie angegeben, ist "Passwortwiederherstellung" kein Entscheidungsproblem.
2. Sie haben nicht bewiesen, dass die "Passwortwiederherstellung" keinen Polynom-Zeitalgorithmus hat, Sie haben lediglich aus intuitiven Gründen argumentiert, dass dies nicht der Fall ist. Nur weil ein Lösungsraum gigantisch ist, heißt das nicht, dass es keine schnellen Algorithmen gibt, um die Lösung zu finden. Zum Beispiel gibt es n! Permutationen eines Satzes von n unterschiedliche Ganzzahlen, aber nur einer wird sortiert aufsteigend, aber wir können es finden n log n Zeit. Für ein lustigeres Beispiel siehe Projekt Euler #67.
3. Selbst wenn Sie "Kennwortwiederherstellung" als Entscheidungsproblem neu gemacht haben und zeigen konnten, dass es keinen Polynom-Zeit-Algorithmus zum Lösen vorliegt, müssen Sie nun beweisen, dass die "Passwortwiederherstellung" NP-Complete ist.

Einzelheiten zu P/NP/etc. Sieh dir das an Vorherige Frage.

Answer 6

Die formale Aussage dieses Problems wäre eine, die als Eingabe des Hashed -Werts (und Salz) und zu finden ist a Passwort, das diesen Hash generiert: Ihr grundlegendes bekannter CypherText -Kollisionsproblem.

Abhängig von der Qualität des Hashs, dies möglicherweise nicht Erfordernis exponentieller Zeit. In der Tat haben viele kryptografische Hashed -in -weit verbreitete Verwendung Angriffe identifiziert, die schneller als Schlüsselspace -Suchanfragen laufen.

Das heißt: Sie (und einige der anderen Responder) haben vermutet Dass die Routine für das Passwort -Munding alle Eigenschaften hat, die die Designer von ihnen haben wollten. Dies müsste sein bewiesen.

Answer 7

Diese Antwort zu schreiben, weil ich diese Idee irgendwann hatte und die Antworten hier nicht zufriedenstellend waren.

Sie haben bewiesen, dass p =/= np unter der Anwesenheit eines 'Orakels' (dies ist das, was zeigt, ob das Passwort richtig ist oder nicht).

Es wurde gezeigt, dass Sie das ursprüngliche P vs -NP nicht mithilfe von Orakel beweisen können (diese Technik wird als Relativisierung bezeichnet).

Um das ursprüngliche Problem zu beweisen, müssen Sie das Orakel in Bezug auf eine Turing -Maschine definieren. Mit anderen Worten, Sie müssen beschreiben, was der Passwortüberprüfer mit der Eingabe macht, und dann beweisen, dass es keinen Algorithmus gibt, der das Kennwort angesichts des Passwort -Verifizierercodes erraten kann.

Beachten Sie, dass Sie dies für einen möglichen schnellen Passwort -Überprüfer tun müssen. Die einzige Anforderung des Kennwortverifiziereralgorithmus besteht darin, dass es in der Polinomzeit in Bezug auf die Passwortlänge ausgeführt wird.

Bei einem möglichen Algorithmus, der überprüft, ob das Passwort in Polinomialzeit richtig ist oder nicht, müssen Sie einen Algorithmus schreiben, der den Verifier -Algorithmus liest, und versucht zu erraten, dass das Passwort in der Polinomialzeit liegt. Wenn Sie beweisen oder widerlegen können, dass ein solcher Algorithmus existiert, haben Sie das Problem gelöst.