Frage

Die Frage, ob P = NP ist vielleicht der berühmteste in allen Informatik. Was heißt das? Und warum ist es so interessant?

Oh, und für zusätzliche Kredite, gibt bitte einen Beweis für die Wahrheit der Aussage oder Lüge. :)

War es hilfreich?

Lösung

P steht für Polynomzeit. NP steht für nicht-deterministisch polynomialer Zeit.

Definitionen:

  • Polynomzeit bedeutet, dass die Komplexität des Algorithmus O (n ^ k) ist, wobei n die Größe der Daten (zB Anzahl von Elementen in einer Liste sortiert werden) ist und k eine konstante ist.

  • Komplexität ist die Zeit in der Anzahl der Operationen gemessen es, in Abhängigkeit von der Anzahl der Datenelemente nehmen würde.

  • Operation ist, was auch immer für eine bestimmte Aufgabe Sinn als Grundbetrieb macht. Für die grundlegende Bedienung Sortierung ist ein Vergleich. Für Matrixmultiplikation ist der Basisbetrieb Multiplikation zweier Zahlen.

Nun ist die Frage, was im Vergleich zu nicht-deterministisch mittlerem deter tut. Es ist ein abstraktes Rechenmodell, ein imaginärer Computer genannt Turingmaschine (TM). Diese Maschine hat eine endliche Anzahl von Zuständen, und ein unendliches Band, die diskreten Zellen, in denen eine endliche Menge von Symbolen geschrieben und gelesen werden kann. Zu jedem gegebenen Zeitpunkt ist der TM in einem seiner Zustände, und es wird an einer bestimmten Zelle auf dem Band suchen. Je nachdem, was er las aus dieser Zelle, kann es ein neues Symbol in diese Zelle schreiben, das Band einer Zelle vorwärts oder rückwärts bewegen, und geht in einen anderen Zustand. Dies wird ein Zustandsübergang genannt wird. Erstaunlicherweise durch vorsichtiges Zustände und Übergänge konstruieren, können Sie ein TM entwerfen, die auf jedem Computer-Programm entspricht, das geschrieben werden kann. Deshalb ist es als theoretisches Modell verwendet wird, für den Nachweis Dinge über das, was Computer kann und nicht tun können.

Es gibt zwei Arten von TM ist das Anliegen uns hier: deterministische und nicht-deterministisch. Eine deterministische TM hat nur einen Übergang von jedem Zustand für jedes Symbol, dass es das Band abliest. Eine nicht-deterministische TM kann mehrere solchen Übergang, i. e. es ist in der Lage, gleichzeitig mehrere Möglichkeiten zu prüfen. Dies ist eine Art, wie mehrere Threads Laichen. Der Unterschied besteht darin, dass eine nicht-deterministische TM kann beliebig viele solche „threads“ Spawn als es will, während auf einem realen Computer nur eine bestimmte Anzahl von Threads zu einem Zeitpunkt ausgeführt werden kann (gleich die Anzahl von CPUs). In Wirklichkeit Computer sind grundsätzlich determinis TMs mit endlichen Bänder. Auf der anderen Seite kann eine nicht-deterministische TM physikalisch nicht realisiert werden kann, außer vielleicht mit einem Quantencomputer.

Es hat sich gezeigt, dass jedes Problem, das von einem nicht-deterministische TM gelöst werden kann, kann durch eine deterministische TM gelöst werden. Es ist jedoch nicht klar, wie viel Zeit es dauern wird. Die Aussage P = NP bedeutet, dass, wenn ein Problem auf einem nicht-deterministischen TM Polynom Zeit in Anspruch nimmt, dann kann man eine deterministische TM bauen, die das gleiche Problem auch in Polynomialzeit lösen würde. Bisher niemand in der Lage gewesen zu zeigen, dass es getan werden kann, aber niemand war in der Lage zu beweisen, dass es nicht getan werden kann, auch nicht.

NP-vollständiges Problem bedeutet ein NP-Problem X, so dass jedes NP-Problem Y zu X durch ein Polynom Reduktion reduziert werden kann. Das bedeutet, dass, wenn jemand jemals mit einer Polynom-Zeit-Lösung auf ein NP-vollständiges Problem kommt, dass auch eine Polynom-Zeit Lösung für jedes NP-Problem geben. Somit wäre das, dass P = NP beweisen. Umgekehrt, wenn jemand ist, dass P beweisen! = NP, dann würden wir sicher sein, dass es keine Möglichkeit gibt, ein NP-Problem in polynomieller Zeit auf einem herkömmlichen Computer zu lösen.

Ein Beispiel für ein NP-vollständiges Problem ist das Problem, eine Wahrheit Zuordnung zu finden, die einen Booleschen Ausdruck mit n Variablen wahr machen würden.
Zur Zeit in der Praxis ein Problem, das Polynom Zeit auf der nicht-deterministische TM nimmt nur in exponentieller Zeit auf einem deterministischen TM oder auf einem herkömmlichen Computer durchgeführt werden.
Zum Beispiel ist der einzige Weg, die Wahrheit Zuordnungsproblem zu lösen 2 ^ n Möglichkeiten zu versuchen.

Andere Tipps

  1. Ein Ja oder kein Problem in P ( P olynomial Zeit), wenn die Antwort in Polynomialzeit berechnet werden.
  2. Ein Ja oder kein Problem in NP ( N auf deterministisches P olynomial Zeit), wenn eine Ja-Antwort sein kann < em> verifiziert in Polynomzeit.

Intuitiv können wir sehen, dass, wenn ein Problem in ist P , dann ist es in NP . eine mögliche Lösung für ein Problem in Da P können wir die Antwort einfach neu zu berechnen, die Antwort überprüfen.

Weniger offensichtlich und viel schwieriger zu beantworten, ist, ob alle Probleme in NP sind in P . Bedeutet die Tatsache, dass wir eine Antwort in polynomialer Zeit verifizieren kann bedeuten, dass wir die Antwort in Polynomialzeit berechnen kann?

Es gibt eine große Anzahl von wichtigen Problemen, die erwiesenermaßen NP -komplette (im Grunde, wenn all diese Probleme nachweislich in sein, P , dann alle NP Probleme in P ). Wenn P = NP , dann alle diese Probleme bewiesen wird eine effiziente (Polynomzeit) Lösung haben.

Die meisten Wissenschaftler glauben, dass P ! = NP . Es wurde jedoch kein Beweis noch für entweder P = etabliert NP oder P ! = NP . Wenn jemand einen Beweis für entweder Vermutung liefert, sie werden US $ 1 Million gewinnen.

Um die einfachste Antwort gebe ich denken kann:

Angenommen, wir haben ein Problem, das eine bestimmte Anzahl von Eingaben nimmt und verschiedene mögliche Lösungen hat, die das Problem nicht löst für bestimmte Eingaben oder nicht. Ein Logik-Puzzle in einem Puzzle-Magazin ein gutes Beispiel wäre: die Eingänge sind die Bedingungen ( „George lebt nicht im blauen oder grünen Hause“) und die mögliche Lösung ist eine Liste von Aussagen ( "George lebt in den gelben Haus, wächst Erbsen und besitzt den Hund "). Ein berühmtes Beispiel ist das Reiseproblem: eine Liste der Städte gegeben, und die Zeiten von jeder Stadt zu jedem anderen zu bekommen, und eine Frist, wäre eine mögliche Lösung eine Liste der Städte in der Reihenfolge sein, der Verkäufer besucht sie, und es würde funktionieren, wenn die Summe der Laufzeiten geringer ist als die Zeit zu begrenzen.

Ein solches Problem ist in NP, wenn wir effizient eine mögliche Lösung überprüfen, um zu sehen, ob es funktioniert. Um zum Beispiel eine Liste der Städte für den Verkäufer zu besuchen, um gegeben, können wir die Zeiten für jede Reise zwischen den Städten addieren, und einfach zu sehen, ob es innerhalb der Frist ist. Ein Problem ist in P, wenn wir effizient eine Lösung finden können, wenn ein solches vorhanden ist.

(Effizient, hier muss eine genaue mathematische Bedeutung. In der Praxis bedeutet dies, dass große Probleme sind nicht unangemessen schwierig zu lösen. Wenn Sie nach einer möglichen Lösung suchen, eine ineffiziente Art und Weise all möglichen Lösungsansätze zur Liste wäre, oder etwas nahe an, dass, während eine effiziente Möglichkeit, eine viel begrenzte Menge der Suche erfordern würde.)

Daher ist die P = NP Problem kann auf diese Weise ausgedrückt werden: Wenn Sie eine Lösung für ein Problem der Art oben effizient beschrieben überprüfen können, können Sie eine Lösung finden (oder beweisen es keine gibt) effizient? Die offensichtliche Antwort ist: „Warum soll man in der Lage sein?“, Und das ist ziemlich viel, wo die Sache heute steht. Niemand konnte es eine oder andere Weise beweisen, und das stört viele Mathematiker und Informatiker. Das ist, warum jemand, der die Lösung für eine Million Dollar aus der Claypool Stiftung liegt unter Beweis stellen kann.

Wir gehen davon aus, dass im Allgemeinen P nicht gleich NP hat, dass es keine allgemeine Art und Weise ist es, Lösungen zu finden. Wenn es stellte sich heraus, dass P = NP, würde eine Menge Dinge ändern. Zum Beispiel würde Kryptographie unmöglich geworden, und mit ihm jede Art von Privatsphäre oder Überprüfbarkeit im Internet. Schließlich können wir den verschlüsselten Text und den Schlüssel effizient nehmen und den ursprünglichen Text produzieren, so dass, wenn P = NP konnten wir effizient den Schlüssel finden, ohne es vorher zu wissen. Knacken von Passwörtern würde trivial. Auf der anderen Seite gibt es ganze Klassen von Planungsproblemen und Ressourcenallokation Problemen, die wir effektiv lösen zu können.

Sie haben möglicherweise die Beschreibung NP-vollständig gehört. Ein NP-vollständiges Problem ist eines, das NP (natürlich) ist, und hat diese interessante Eigenschaft: Wenn es in P ist, jedes NP-Problem ist, und so P = NP. Wenn Sie einen Weg finden könnten, um effizient das Reiseproblem zu lösen, oder Logik-Puzzles aus Puzzle Zeitschriften, können Sie effizient alles in NP lösen. Ein NP-vollständiges Problem ist, in einer Weise, die härteste Art von NP-Problem.

Wenn Sie also eine effiziente allgemeine Lösungstechnik für jedes NP-vollständiges Problem finden können, oder beweisen, dass keine solche vorhanden ist, Ruhm und Reichtum ist bei Ihnen.

Eine kurze Zusammenfassung von meinem bescheidenen Wissen:

Es gibt einige einfachen Rechenprobleme (wie den kürzesten Weg in einem Graphen zwischen zwei Punkten zu finden), die ziemlich schnell berechnet werden können (O (n ^ k), wobei n die Größe des Eingangs und k eine Konstante (im Fall von Graphen, es ist die Anzahl von Eckpunkten oder Kanten)).

Andere Probleme, wie einen Weg zu finden, die jede Ecke in einem Graphen kreuzt oder sich die privaten RSA-Schlüssel aus dem öffentlichen Schlüssel ist härter (O (e ^ n)).

Aber CS sprechen erzählt, dass das Problem ist, dass wir eine nicht-deterministische Turing-Maschine zu einem deterministisch man nicht ‚umwandeln‘ können, können wir jedoch verwandeln nicht-deterministische endliche Automaten (wie die Regex-Parser) in determinis ( na ja, Sie können, aber die Laufzeit der Maschine wird lange dauern). Das heißt, wir müssen jeden möglichen Weg versuchen (in der Regel intelligent CS Professoren können ein paar diejenigen ausschließen).

Es ist interessant, weil noch niemand eine Ahnung von der Lösung hat. Einige sagen, es ist wahr, einige sagen, es ist falsch, aber es gibt keinen Konsens. Eine weitere interessante Sache ist, dass eine Lösung für den öffentlichen / privaten Schlüssel Verschlüsselungen (wie RSA) schädlich sein würde. Man könnte sich als leicht bricht einen RSA-Schlüssel als Generierung jetzt ist.

Und es ist ein ziemlich inspirierend Problem.

Es gibt nicht viel, was ich zu dem hinzufügen, was und warum der P = NP Teil der Frage, aber in Bezug auf den Beweis. Nicht nur wäre ein Beweis einige zusätzliche Kredite wert, aber es wäre eine der veröffentlichte Ergebnisse (PDF) auf jeden Fall wert ist in Bezug auf den Gegenstand eines Beweises zu lesen.

Zunächst einige Definitionen:

  • Ein besonderes Problem in P ist, wenn Sie eine Lösung in der Zeit von weniger als n^k für einige k berechnen können, wo n die Größe des Eingangs. Zum Beispiel kann das Sortieren in n log n erfolgen, die weniger als n^2 ist, so Sortier Polynomzeit ist.

  • Ein Problem in NP ist, wenn es eine k existiert, so dass es eine Lösung Größe höchstens n^k existiert, die Sie in der Zeit höchstens n^k überprüfen können. Nehmen Sie 3-Färbung von Graphen: Da eine grafische Darstellung, eine 3-Färbung ist eine Liste von (Vertex, Farbe) Paare, die Größe O(n) hat und Sie können in der Zeit O(m) (oder O(n^2)) überprüfen, ob alle Nachbarn verschiedene Farben haben. So ein Graph ist 3-färbbar nur, wenn es eine kurze und leicht nachprüfbar Lösung ist.

Eine äquivalente Definition von NP ist "Probleme durch eine lösbaren N ondeterministic Turing Maschine in P olynomial time". Während das Ihnen sagt, wo der Name herkommt, ist es nicht geben Ihnen die gleiche intuitive Gefühl von dem, was NP-Probleme sind wie.

Beachten Sie, dass P eine Teilmenge von NP ist: wenn Sie eine Lösung in polynomialer Zeit finden kann, gibt es eine Lösung, die in polynomieller Zeit überprüft werden kann - nur prüfen, ob die gegebene Lösung der gleich eins ist Sie finden können.

Warum ist die Frage P =? NP interessant? Um das zu beantworten, ein erstes muss sehen, was NP-vollständige Probleme sind. Einfach gesagt,

  • Ein Problem L NP-vollständig ist, wenn (1) L in P ist, und (2) ein Algorithmus, der L löst verwendet wird, kann kein Problem L‘in NP zu lösen; das heißt, eine Instanz von L gegeben ‚können Sie eine Instanz von L erstellen, die eine Lösung, wenn und nur wenn die Instanz von L‘ bietet eine Lösung hat. Formal gesehen ist jedes Problem L‘in NP reduzierbar L.

Beachten Sie, dass die Instanz von L Polynomialzeit berechenbar und hat Polynom Größe sein muss, in der Größe L '; auf diese Weise, ein NP-vollständiges Problem in Polynomialzeit Lösung gibt uns eine Polynomzeit Lösung alle NP-Probleme.

Hier ist ein Beispiel: Angenommen, wir wissen, dass 3-Färbung von Graphen ein NP-hard Problem. Wir wollen beweisen, dass die Erfüllbarkeit der Booleschen Formeln entscheiden ist ein NP-hard Problem auch.

Für jede Ecke v, hat zwei boolean Variablen V_h und V_L, und die Anforderung (V_h oder V_L): jedes Paar nur die Werte {01, 10, 11}, die wir als Farbe 1 denken können, 2 und 3.

Für jede Kante (u, v), haben die Anforderung, dass (u_h, U_L)! = (V_h, V_L). Das heißt,

  

not ((u_h and not u_l) and (v_h and not v_l) or ...)   keiner von ihnen Aufzählen alle gleich Konfigurationen und Bestimmung, dass es der Fall ist.

AND'ing zusammen all diese Einschränkungen gibt einen Booleschen Formel, die Polynom Größe hat (O(n+m)). Sie können prüfen, ob es Polynom Zeit in Anspruch nimmt und zu berechnen. Sie einfach O(1) Sachen pro Vertex und pro Kante tun

Wenn Sie die Boolesche Formel lösen kann ich gemacht habe, dann lösen Sie können auch Graphenfärbungs: für jedes Paar von Variablen V_h und V_L, lassen Sie die Farbe v derjenige sein, der die Werte dieser Variablen entsprechen. Durch die Konstruktion der Formel Nachbarn nicht gleich Farben haben.

Wenn also 3-Färbung von Graphen NP-vollständig ist, so ist boolean-Formel-Erfüllbarkeit.

Wir wissen, dass 3-Färbung von Graphen ist NP-vollständig; aber historisch sind wir gekommen, zu wissen, dass, indem zuerst die NP-Vollständigkeit des boolean schluß Erfüllbarkeit zeigt, und dann verringert wird, dass 3-Färbbarkeit (statt umgekehrt).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top