Als Beispiel nehmen wir das Faktorisierungsverfahren<\/a>, auf dem sehr viele kryptographische Algorithmen (u.a. RSA<\/a>\u00a0oder das Verfahren von Diffie-Hellmann<\/a> zum Schl\u00fcsselaustausch) basieren. Diese Algorithmen gehen davon aus, dass das Faktorisierungsproblem nicht effizient zu l\u00f6sen ist. Es w\u00e4re das blanke Chaos, w\u00fcrde sich herausstellen, dass \\(P=NP\\). \\(P\\neq NP\\) w\u00e4re hingegen nicht so schlimm.<\/p>\n Machen wir uns einmal klar, was \\(P\\) und \\(NP\\) denn nun wirklich sind. Dazu betrachten wir zun\u00e4chst eine etwas gr\u00f6\u00dfere Klasse.<\/p>\n Klassifizierung<\/strong> \\(EXPTIME\\)<\/p>\n In \\(EXPTIME\\) liegen Probleme, die auf einer deterministischen Turingmaschine in \\(O(2^n)\\), d.h. in exponentieller Zeit, entschieden werden k\u00f6nnen. Hier ist \\(n\\) die Eingabel\u00e4nge.<\/p>\n Es ist nicht schwer zu sehen, dass man hier nur f\u00fcr sehr kleine Probleminstanzen effizient nach einer L\u00f6sung suchen kann. F\u00fcr gr\u00f6\u00dfere Eingabel\u00e4ngen \\(n\\) wird die Suche ungleich schwerer.<\/p>\n Was w\u00e4re so ein Problem, dass deterministisch in exponentieller Zeit l\u00f6sbar w\u00e4re? Na klar, das Problem des Handlungsreisenden<\/a> (auch TSP, travelling salesman, genannt). Der folgende Abschnitt basiert mehrheitlich auf dem Artikel aus der Wikipedia.<\/p>\n Beispiel\u00a0TSP<\/strong><\/p>\n Das TSP geh\u00f6rt zur der Klasse der Optimierungsprobleme. Bei diesem Problem geht es darum f\u00fcr eine gegebene Anzahl St\u00e4dte und einer Entfernung zwischen diesen den k\u00fcrzesten Weg f\u00fcr einen Rundkurs zu finden.<\/p>\n Diese Problem hat eine Vielzahl an Anwendungsm\u00f6glichkeiten (Logistik, Design von Mikrochips, etc.), so dass eine optimale L\u00f6sung durchaus w\u00fcnschenswert erscheint.<\/p>\n Leider haben wir hier, in Abh\u00e4ngigkeit der Anzahl der zu besuchenden Punkte, nur dann eine optimale L\u00f6sung wenn wir jeden Punkt pr\u00fcfen. Das Wachstum ist also exponentiell und zweifellos geh\u00f6rt TSP zur Klasse \\(EXPTIME\\), zumindest bei seinem deterministischen L\u00f6sungsansatz.<\/p>\n Auch wenn mittlerweile f\u00fcr mehrere Tausend Punkte optimale L\u00f6sungen durch heuristische und exakte Verfahren gefunden wurden, so bleibt das Problem gleich: mit wachsendem \\(n\\) (der Anzahl der Punkte) steigt unser Aufwand immer noch exponentiell.<\/p>\n Graphisch ausgedr\u00fcckt (geklaut aus der Wikipedia):<\/p>\n Frage: Wie ist der k\u00fcrzeste Weg von \\(A\\) nach \\(A\\) \u00fcber alle Punkte? <\/em><\/p>\n W\u00e4hrend das bei \\(4\\) Punkten noch einfach ist, wird es f\u00fcr \\(100.000\\) Punkte schon deutlich schwerer.<\/p>\n Es sind derzeit nur effiziente, heuristische Algorithmen<\/strong> bekannt, die die L\u00f6sung approximieren. Z.B. der Algorithmus von Christofides<\/a>, der in polynomieller Laufzeit eine L\u00f6sung approximieren kann, die maximal \\(1.5\\) Mal so lang ist wie die optimale L\u00f6sung.<\/p>\n F\u00fcr exakte L\u00f6sungen gilt: jede Rundreise muss berechnet und die k\u00fcrzeste ausgew\u00e4hlt werden. Bei \\(15\\) St\u00e4dten haben wir \\(43\\) Mrd. M\u00f6glichkeiten. Hat man einen Rechner, der die L\u00f6sung f\u00fcr \\(30\\) St\u00e4dte in einer Stunde berechnet, dann braucht dieser f\u00fcr zwei zus\u00e4tzliche St\u00e4dte ann\u00e4hernd die tausendfache Zeit; das sind mehr als \\(40\\) Tage.<\/p>\n Die Folien<\/a> der RWTH Aachen<\/a> zeigen eine sch\u00f6ne Tabelle, die ich hier Snapshotten m\u00f6chte:<\/p>\n Das Beispiel f\u00fchrt vor Augen, dass uns sehr daran gelegen, dass wir Probleme nicht in Exponentialzeit l\u00f6sen m\u00fcssen.<\/p>\n Nachdem wir die Optimierungsvariante<\/strong> haben, kommen wir zum Bindeglied des \\(TSP\\) zu der Klasse \\(NP\\): uns geht es zun\u00e4chst nicht um Optimierung, sondern um eine Entscheidung.<\/p>\n Die Entscheidungsvariante<\/strong> des \\(TSP\\) ist:<\/p>\n Gibt es eine Tour mit Kosten \\({}\\leq b\\)?<\/p>\n<\/blockquote>\n Und hier beginnt unsere Reise: w\u00e4hrend wir hier wieder alle Wege durchprobieren und so in der Klasse der Exponentialzeit-Algorithmen landen, k\u00f6nnen wir uns das Leben deutlich einfacher machen. Aber dazu gleich mehr.<\/p>\n Ich gehe auf das \\(TSP\\) nun nicht weiter ein, da es mir nur um \\(P-NP\\) geht und die Ausf\u00fchrungen bis hierhin f\u00fcr diese Betrachtung ausreichen.<\/p>\n Kleiner Exkurs zum Schluss: Durch die Hierarchies\u00e4tze<\/a> k\u00f6nnen wir z.B. zeigen, dass \\(P\\subsetneq EXPTIME\\) ist. Damit gibt es in \\(EXPTIME\\) Probleme, die nicht in \\(P\\) liegen.<\/p>\n Klassifizierung<\/strong> \\(P\\)<\/p>\n Ein Problem in \\(P\\) bedeutet, dass es effizient l\u00f6sbar<\/strong> ist. Effizient hei\u00dft: die deterministische Turingmaschine, die das Problem l\u00f6st ist nach oben durch ein Polynom \\(n^k\\) beschr\u00e4nkt, wobei \\(n\\) die L\u00e4nge der Eingabe ist. Wichtig hieran ist: \\(k\\) ist zwar beliebig, aber absolut unabh\u00e4ngig von unserer Eingabe!<\/p>\n Ein Beispiel f\u00fcr ein Problem in der Komplexit\u00e4tsklasse \\(P\\) ist das \\(PRIMES\\).<\/p>\n Beispiel<\/strong> \\(PRIMES\\)<\/p>\n Hier ist die Frage ob eine Zahl \\(x\\) eine Primzahl ist oder nicht.<\/p>\n Die Antwort auf diese Frage ist ziemlich simpel: wir testen einfach aus ob alle Zahlen von \\(2\\) bis \\(x-1\\) unsere Zahl \\(x\\) ohne Rest teilen k\u00f6nnen. Wenn das nicht der Fall ist, ist die Zahl eine Primzahl.<\/p>\n Mit dem AKS-Algorithmus<\/a> gibt es sogar einen, der das in Polynomzeit entscheiden kann. Damit geh\u00f6rt \\(PRIMES\\) tats\u00e4chlich zur Komplexit\u00e4tsklasse \\(P\\).<\/p>\n Nach dem der Urvater der AKS-Algorithmen gefunden wurde, wurden weitere ersonnen, die die Laufzeit noch ein St\u00fcck nach unten korrigierten. Der schnellste bekannte Algorithmus aus der AKS-Familie terminiert in \\(O((log\\text{ }N)^{6+\\varepsilon})\\).<\/p>\n Kommen wir nun zur Komplexit\u00e4tsklasse, die uns so brennend interessiert.<\/p>\n Klassifizierung<\/strong> \\(NP\\)<\/p>\n Ist ein Problem in \\(NP\\), so bedeutet es, dass es effizient pr\u00fcfbar<\/strong> ist. In diesem Fall hei\u00dft effizient ebenfalls: die deterministische Turingmaschine, die pr\u00fcft ob das Zertifikat \\(z\\) zum Problem \\(X\\) (ein Zertifikat ist ein L\u00f6sungsvorschlag f\u00fcr ein Problem), ist nach oben durch ein Polynom \\(n^k\\) beschr\u00e4nkt, wobei \\(n\\) die L\u00e4nge der Eingabe ist.<\/p>\n Gemerkt, was der Unterschied zwischen \\(NP\\) und \\(P\\) ist? Es ist ein Unterschied ob wir ein Problem l\u00f6sen oder „nur“ einen L\u00f6sungsvorschlag pr\u00fcfen.<\/p>\n Was bedeutet es f\u00fcr unser \\(TSP\\)?<\/p>\n Beispiel<\/strong> \\(TSP\\)-Instanz<\/strong><\/p>\n Nehmen wir unsere \\(4\\) Punkte aus dem obigen Beispiel und stellen uns die Frage:<\/p>\n Gibt es einen Weg von \\(A\\) nach \\(A\\) mit L\u00e4nge \\({}\\leq{100}\\)?<\/em><\/p>\n Das ist ein Entscheidungsproblem. Und hier m\u00fcssten wir im schlimmsten Fall nun alle Wege durchprobieren bis wir einen Weg finden, der k\u00fcrzer als\/gleich \\(100\\) ist. Was bei vielen Punkten schon eine betr\u00e4chtliche Zeit in Anspruch nehmen kann, wie wir gesehen haben. Dieses „Durchprobieren“ ist genau unser \\(N\\) aus \\(NP\\). Das Orakeln einer L\u00f6sung.<\/p>\n Lassen wir das Orakeln weg und geben eine L\u00f6sung vor, bleibt nur noch \\(P\\): die Pr\u00fcfung einer gegebenen L\u00f6sung auf ihre Korrektheit. Und das k\u00f6nnen wir ziemlich zackig bewerkstelligen:<\/p>\n Wir pr\u00fcfen die Kanten zwischen den Knoten und rechnen sie einfach zusammen:<\/p>\n \\(A\\rightarrow{C}\\rightarrow{D}\\rightarrow{B}\\rightarrow{A}\\Rightarrow{{42}\\rightarrow{12}\\rightarrow{34}\\rightarrow{20}=108}\\)<\/p>\n Nope, das war nichts. Versuchen wir es mit:<\/p>\n \\(A\\rightarrow{D}\\rightarrow{C}\\rightarrow{B}\\rightarrow{A}\\Rightarrow{{35}\\rightarrow{12}\\rightarrow{30}\\rightarrow{20}=97}\\)<\/p>\n Bingo!<\/p>\n Man sieht leicht, dass wir zur Pr\u00fcfung einer vorgegebenen L\u00f6sung auf einer deterministischen Turingmaschine deutlich weniger Zeit ben\u00f6tigen als alle Wege durchzuprobieren.<\/p>\n Und nun holen wir uns unser \\(N\\) aus \\(NP\\), indem wir orakeln. Wir raten einfach alle Kombinationen und pr\u00fcfen sie polynomiell durch unsere deterministische „Kontrollturingmaschine“.<\/p>\n Im Schlimmsten Fall haben wir zwar immer noch einen exponentiellen Aufwand, aber vielleicht raten wir so gut, dass die Kombination \\(A\\rightarrow{D}\\rightarrow{C}\\rightarrow{B}\\rightarrow{A}\\)\u00a0die erste geratene M\u00f6glichkeit ist und wir schon nach dem ersten Orakeln eine L\u00f6sung gefunden haben.<\/p>\n Und genau das bedeutet \\(NP\\): raten und pr\u00fcfen. Oder ganz, ganz frei interpretiert: Orakel\\(N\\) und \\(P\\)r\u00fcfen.<\/p>\n Codieren wir den Graphen als Turingmaschine, so hat z.B. der Zustand \\(A\\) drei m\u00f6gliche Folgezust\u00e4nde (wir k\u00f6nnen zu \\(B\\), \\(C\\) oder \\(D\\) reisen). Es existieren also drei m\u00f6gliche Zustands\u00fcberg\u00e4nge, von denen wir einen w\u00e4hlen k\u00f6nnen. Genau hier beginnt das Raten\/Orakeln, unser \\(N\\) aus \\(NP\\). Anschlie\u00dfend haben wir zwei M\u00f6glichkeiten zur Auswahl, usw.<\/p>\n So geht dann unsere \\(NTM\\) f\u00fcr das \\(TSP\\) vor und r\u00e4t eine Rundreise. Wir brechen ab wenn die Kosten h\u00f6her sind als \\(b\\) oder wir bei unserem Ausgangsknoten landen ohne alle Knoten besucht zu haben.<\/p>\n Zusammenfassend l\u00e4sst sich sagen: \\(NP\\) bedeutet orakeln und pr\u00fcfen. Und das Pr\u00fcfen geschieht in maximal polynomieller Zeit.<\/p>\n Habt Ihr nun ein Gef\u00fchl daf\u00fcr, was \\(NP\\) bedeutet? Gut.<\/p>\n Nachdem wir nun alle notwendigen Komplexit\u00e4tsklassen \\(EXPTIME\\), \\(P\\) und \\(NP\\) besprochen haben, sollte euch klar sein wie der Zusammenhang zwischen \\(P\\) und \\(NP\\) ist.<\/p>\n Jetzt k\u00f6nnen wir auch die Frage stellen, die das \\(P-NP\\)-Problem beschreibt:<\/p>\n Gilt \\(P=NP\\) oder \\(P\\neq{NP}\\)?<\/em><\/p>\n In Worten:<\/p>\n Sind die Klassen \\(P\\) und \\(NP\\) gleich oder nicht, <\/em><\/p>\n bzw.<\/p>\n kann jede Sprache, die nicht-deterministisch in Polynomzeit entschieden werden kann auch deterministisch in Polynomzeit entschieden werden?<\/em><\/p><\/blockquote>\n Derzeit gehen Graphisch aufgearbeitet sieht die hier beleuchtete, problematische Beziehung zwischen \\(P\\) und \\(NP\\) so aus:<\/p>\n![\"tsm\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/07\/tsm.png\")
<\/a><\/p>\n![\"tsm_aachen\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/07\/tsm_aachen.png\")
<\/a><\/p>\n\n
alle<\/del>\u00a0die meisten von letzterem aus. Die Folgen w\u00e4ren, wie gesagt, \u00fcbersichtlich wenn das stimmt. Daf\u00fcr m\u00fcssten wir nur zeigen, dass es in \\(NP\\) Probleme gibt, die definitiv nicht deterministisch polynomiell l\u00f6sbar, also nicht in \\(P\\) sind.<\/p>\n![\"pnpklassen\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/07\/pnpklassen.png\")
<\/a><\/p>\n