{"id":3659,"date":"2012-03-05T20:29:19","date_gmt":"2012-03-05T19:29:19","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=3659"},"modified":"2023-05-16T08:27:19","modified_gmt":"2023-05-16T06:27:19","slug":"das-p-np-problem-teil-2-p-und-np","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2012\/03\/das-p-np-problem-teil-2-p-und-np.htm","title":{"rendered":"Das P-NP-Problem, Teil 2: P und NP"},"content":{"rendered":"<div style='text-align:right;'><small>(<a href='https:\/\/www.herr-rau.de\/wordpress\/2012\/03\/das-p-np-problem-teil-2-p-und-np.htm#comments'>6 Kommentare.<\/a>)<\/small> <\/div>\n<p><strong><em>Executive summary: Es gibt eine besondere Art von Fragen, die schwer zu beantworten sind, aber wenn man die Antwort hat, kann man relativ leicht \u00fcberpr\u00fcfen, ob sie auch wirklich stimmt.<\/em><\/strong><\/p>\n\n\n\n<p>(<a href=\"https:\/\/www.herr-rau.de\/wordpress\/2012\/03\/das-p-np-problem-teil-1-was-schwierig-ist.htm\">Fortsetzung vom letzten Mal.<\/a>) Als grobe Faustregel &#8211; und wir sind ja hier nur am Groben interessiert &#8211; kann man sagen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>alle Fragen, f\u00fcr die sich mit linear steigendem Aufwand eine Antwort finden l\u00e4sst, sind in der Praxis gut beantwortbar (und bei konstantem Aufwand sowieso)<\/li>\n\n\n\n<li>alle Fragen, f\u00fcr die sich mit polynomiell steigendem Aufwand eine Antwort finden l\u00e4sst, sind in der Praxis gut beantwortbar<\/li>\n\n\n\n<li>alle Fragen, f\u00fcr die sich nur mit exponentiell steigendem Aufwand eine Antwort finden l\u00e4sst, sind in der Praxis nur schwer zu beantworten (allerdings gibt es f\u00fcr manche dieser Aufgaben schnellere L\u00f6sungsverfahren, die zwar nicht das perfekte, aber immerhin ein halbwegs brauchbares Ergebnis liefern)<\/li>\n<\/ul>\n\n\n\n<p>Faustregel deshalb, weil eine exponentielle L\u00f6sung bei sehr kleinem Exponenten und kleinen Ausgangswerten schneller sein kann als eine polynomielle L\u00f6sung hoher Ordnung. Soll uns jetzt nicht k\u00fcmmern.<\/p>\n\n\n\n<p>Die Klasse aller Aufgaben mit h\u00f6chstens polynomiell steigendem Aufwand f\u00fcr das <em>L\u00f6sen<\/em> einer Aufgabe nennt man <strong>P.<\/strong> Das schlie\u00dft die ersten der drei F\u00e4lle oben ein. Aufgaben in P sind in der Praxis gut machbar, auch wenn P nicht f\u00fcr &#8222;Praxis&#8220; steht, sondern f\u00fcr &#8222;polynomiell&#8220;. Typische Aufgaben in P sind das Sortieren und Durchsuchen von Listen und das Finden k\u00fcrzester Wege auf einer Stra\u00dfenkarte.<\/p>\n\n\n\n<p>Und dann gibt es noch eine andere Klasse von Aufgaben, die hei\u00dft <strong>NP.<\/strong> Da sind die Aufgaben drin, f\u00fcr die man mit h\u00f6chstens polynomiellem Aufwand <em>\u00fcberpr\u00fcfen<\/em> kann, ob eine L\u00f6sung die richtige ist, wenn man sie denn einmal hat. (Das schlie\u00dft alle Aufgaben aus P mit ein.)<\/p>\n\n\n\n<p>Daneben gibt es noch weitere Klassen, also zum Beispiel die Klasse <strong>EXPTIME.<\/strong> Da sind die Aufgaben drin, f\u00fcr die man mit h\u00f6chstens exponentiellem Zeitaufwand eine L\u00f6sung finden kann. (Das schlie\u00dft alle Aufgaben aus NP ein, und dann nat\u00fcrlich P sowieso. Aber dazu eben auch die Aufgaben, f\u00fcr die selbst das \u00dcberpr\u00fcfen einer vorgeschlagenen L\u00f6sung sehr viel Arbeit macht.) Dazwischen und davor und dahinter und drumherum gibt es noch weitere Klassen, aber diese drei reichen uns hier. Ihr Verh\u00e4ltnis zueinander sieht man in diesem Diagramm:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"550\" height=\"308\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/komplexitaet_klassen.jpg\" alt=\"\" class=\"wp-image-3678\" title=\"komplexitaet_klassen\" srcset=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/komplexitaet_klassen.jpg 550w, https:\/\/www.herr-rau.de\/wordpress\/archiv\/komplexitaet_klassen-150x84.jpg 150w\" sizes=\"auto, (max-width: 550px) 100vw, 550px\" \/><\/figure>\n\n\n\n<p><strong>Was gibt es denn f\u00fcr Aufgaben, die schwer zu l\u00f6sen, aber relativ leicht oder auch sehr leicht zu \u00fcberpr\u00fcfen sind, also diejenigen Aufgaben, die in NP liegen, aber au\u00dferhalb von P?<\/strong><\/p>\n\n\n\n<p>Aus <em>Im Laybrinth des Denkens<\/em> von William Poundstone habe ich folgende sch\u00f6ne Idee. Da geht es um ein allwissendes Orakel, das beweisen soll, dass es allwissend ist. Man kann ihm solche Fragen stellen wie: &#8222;Was ist die zweibillionste Dezimalstelle von Pi?&#8220;, und es wird die Antwort ausspucken. Leider kann man die Antwort nicht so ohne Weiteres \u00fcberpr\u00fcfen, weil man das nirgendwo nachschlagen kann und das noch niemand ausgerechnet hat und das auch nicht so einfach auszurechnen ist &#8211; also wird die Antwort niemanden davon \u00fcberzeugen, dass das Orakel wirklich allwissend ist.<br>Man kann das Orakel auch fragen: &#8222;Was ist die Quadratwurzel von 622521?&#8220;, und die Antwort wird ausgespuckt. Aber da k\u00f6nnten Zweifler sagen, dass das Orakel irgendwo einen Taschenrechner oder einen Spickzettel hat oder einfach ziemlich gut rechnen kann. Die Frage ist also zu leicht, als dass sie ein Beweis f\u00fcr die Allwissenheit des Orakel w\u00e4re.<br>Was man braucht, ist eine Frage, bei der es sehr, sehr schwer ist, die Antwort herauszufinden, selbst mit einem Taschenrechner oder Spickzettel oder Assistenten &#8211; aber wenn man sie einmal hat, kann man die Richtigkeit der L\u00f6sung schnell \u00fcberpr\u00fcfen. Und das sind eben die Aufgaben in NP, die au\u00dferhalb von P sind.<\/p>\n\n\n\n<p>Dazu geh\u00f6rt zum Beispiel die Primfaktorenzerlegung. Es sieht auf den ersten Blick vielleicht nicht so aus, aber die Aufgabe, eine beliebige Zahl in Primfaktoren zu zerlegen, w\u00e4chst exponentiell zur Gr\u00f6\u00dfe der Zahl. Die f\u00fcnfstellige Zahl 95477 in ihre zwei Primfaktoren zu zerlegen, das macht schon einigen Aufwand. F\u00fcr einen Computer ist das aber noch leicht. Die doppelt so lange Zahl 3620188223 in ihre beiden Faktoren zu zerlegen, das macht aber nicht doppelt so viel Aufwand, und nicht zehnmal so viel Aufwand, sondern exponentiell mehr Aufwand. Und irgendwann, ab ein paar hundert Dezimalstellen, wird das auch f\u00fcr Computer praktisch nicht mehr berechenbar. Die L\u00f6sung zu \u00fcberpr\u00fcfen, das ist aber wieder einfach &#8211; das ist dann ja nur eine Multiplikation zweier Primzahlen.<\/p>\n\n\n\n<p>Und mit diesen Primfaktoren funktioniert zumindest zum Teil auch die Verschl\u00fcsselung vieler Seiten und Nachrichten im Internet. Man schreit sozusagen heraus: &#8222;Huhu, ich habe hier ein seeeehr gro\u00dfes Produkt zweier Primzahlen. D\u00fcrft ihr euch alle anschauen, und wenn ihr die Zahl in ihre Faktoren zerlegen k\u00f6nnt, dann k\u00f6nnt ihr auch meine verschl\u00fcsselten Nachrichten lesen. Aber elleb\u00e4tsch, das schafft ihr nicht!&#8220;<\/p>\n\n\n\n<p>Mehr Beispiele f\u00fcr diese Art Aufgaben kommen im n\u00e4chsten Teil dieser Eintragserie. Eigentlich geh\u00f6ren nur Fragen, die sich mit ja\/nein beantworten lassen (&#8222;Entscheidungsprobleme&#8220;) in die Kategorie P\/NP; ich war beim Formulieren oben da nicht immer exakt.<\/p>\n\n\n\n<p><strong>Der Vollst\u00e4ndigkeit halber: Was gibt es denn f\u00fcr Aufgaben, die schwer zu l\u00f6sen sind (exponentieller Aufwand), und wo die \u00dcberpr\u00fcfung ebenfalls schwer ist (exponentieller Aufwand)?<\/strong><\/p>\n\n\n\n<p>Ein richtig sch\u00f6nes Beispiel habe ich nicht gefunden. Wenn ein Sch\u00fcler f\u00fcr n Vergehen 2<sup>n<\/sup> mal den Satz schreiben muss &#8222;Ich werde das nie wieder tun&#8220;, dann erfordert die Kontrolle, ob er seine Strafaufgabe gemacht hat, ebenfalls exponentiellen Aufwand (des Z\u00e4hlens). Vielleicht kommt hier irgendwann mal ein sch\u00f6neres Beispiel hin.<\/p>\n\n\n\n<p><strong>Und zum Schluss und als Ausblick f\u00fcr eventuelle sp\u00e4tere Blogeintr\u00e4ge:<\/strong><\/p>\n\n\n\n<p>(1) Es gibt Aufgaben, die man nie berechnen k\u00f6nnen wird, weil man wei\u00df, dass man das prinzipiell nicht berechnen kann. Zum Beispiel kann man kein Computerprogramm schreiben, dass zwei <em>beliebige<\/em> andere Programme unter allen Umst\u00e4nden und immer zum gleichen Ergebnis kommen.<br>(2) Es gibt Aufgaben, die man nie berechnen k\u00f6nnen wird, weil sie zwar eine L\u00f6sung haben, man das aber nie beweisen kann. Ein Beispiel dazu kann man nicht geben, weil, ja, weil man das ja nicht wissen kann.<br>(3) Es gibt Aufgaben, die garantiert eine L\u00f6sung haben, was man auch beweisen kann, die man aber nie wird berechnen k\u00f6nnen (Busy-Beaver-Funktion), weil &#8211; hm, das ist schwer zu erkl\u00e4ren.<\/p>\n\n\n\n<p><small>(Und insgesamt k\u00fcrze ich ein ein bisschen ab. Mit Aufgaben meine ich immer: Fragen, und mit L\u00f6sungen: Antworten. Ist hier nicht so wichtig.)<\/small><\/p>\n\n\n\n<p>(<a href=\"https:\/\/www.herr-rau.de\/wordpress\/2012\/03\/das-p-np-problem-teil-3-pnp.htm\">Fortsetzung folgt.<\/a>)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>(6 Kommentare.) Executive summary: Es gibt eine besondere Art von Fragen, die schwer zu beantworten sind, aber wenn man die Antwort hat, kann man relativ leicht \u00fcberpr\u00fcfen, ob sie auch wirklich stimmt. (Fortsetzung vom letzten Mal.) Als grobe Faustregel &#8211; und wir sind ja hier nur am Groben interessiert &#8211; kann man sagen: Faustregel deshalb, [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":3669,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[25],"tags":[227],"class_list":["post-3659","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-informatik","tag-informatik"],"jetpack_featured_media_url":"https:\/\/www.herr-rau.de\/wordpress\/archiv\/komplexitaet_alle.jpg","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/3659","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=3659"}],"version-history":[{"count":2,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/3659\/revisions"}],"predecessor-version":[{"id":56686,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/3659\/revisions\/56686"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media\/3669"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=3659"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=3659"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=3659"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}