{"id":3679,"date":"2012-03-07T06:23:32","date_gmt":"2012-03-07T05:23:32","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=3679"},"modified":"2023-05-16T08:32:10","modified_gmt":"2023-05-16T06:32:10","slug":"das-p-np-problem-teil-3-pnp","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2012\/03\/das-p-np-problem-teil-3-pnp.htm","title":{"rendered":"Das P-NP-Problem, Teil 3: P=NP?"},"content":{"rendered":"
(1 Kommentare.<\/a>)<\/small> <\/div>\n

Executive summary: Die Fragen vom letzten Mal sind sich alle irgendwie \u00e4hnlich: Wenn man f\u00fcr eine davon einen effizienten L\u00f6sungsweg gefunden hat, kann man den auf die anderen \u00fcbertragen. Wird man je einen finden?<\/em><\/strong><\/p>\n\n\n\n

Hier zur Erinnerung noch einmal der Ausschnitt aus den Komplexit\u00e4tsklassen vom letzten Mal<\/a>:
\"\"<\/p>\n\n\n\n

    \n
  1. In P, da liegen die relativ einfachen Aufgaben.<\/li>\n\n\n\n
  2. In NP (aber au\u00dferhalb von P), da liegen die schweren Aufgaben, bei denen sich die L\u00f6sung wenigstens leicht \u00fcberpr\u00fcfen l\u00e4sst. Die Zeichnung geht davon aus, dass P eine echte Teilmenge von NP ist, was nicht unbedingt stimmen muss.<\/li>\n\n\n\n
  3. In EXPTIME (aber au\u00dferhalb von NP), da liegen die schweren Aufgaben, bei denen sich die L\u00f6sung auch nur schwer \u00fcberpr\u00fcfen l\u00e4sst.<\/li>\n<\/ol>\n\n\n\n

    Der Handlungsreisende<\/strong><\/p>\n\n\n\n

    Viele der Aufgaben aus (2) spielen in der Praxis eine gro\u00dfe Rolle. Ein Beispiel daf\u00fcr ist das Problem des Handlungsreisenden (Travelling Salesman). Das geht von einer Reihe von Orten aus, die zum Teil durch Stra\u00dfen miteinander verbunden sind, etwa so:<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    Die Buchstaben stehen f\u00fcr die Ortsnamen, die Verbindungen dazwischen sind die Stra\u00dfen. Das Ziel des Handlungsreisenden ist es, alle Orte zu besuchen, und zwar derart, dass er insgesamt m\u00f6glichst wenig Entfernung zur\u00fccklegt und am Schluss wieder an seinem Ausgangspunkt ankommt. Die Aufgabe f\u00fcr ein Programm lautet etwa: Nenne mir eine solche Rundreise (wenn es sie denn gibt), die h\u00f6chstens die L\u00e4nge 9 hat. Wenn<\/em> man erst einmal die L\u00f6sung hat, kann man recht einfach \u00fcberpr\u00fcfen, ob sie stimmt. Einfach hei\u00dft: in h\u00f6chstens polynomieller Zeit. In diesem Beispielgraphen ist das sowieso sehr leicht. Dass<\/em> es eine L\u00f6sung gibt, ist auch klar: zur Not probiert man einfach alle m\u00f6glichen Kombinationen aus und schaut, ob eine geeignete dabei ist. Allerdings steigt der Aufwand daf\u00fcr exponentiell mit der Anzahl an Orten und Verbindungen, wenn man eine allgemeine L\u00f6sungsweg hat. (N\u00e4herungsweise L\u00f6sungen gibt es sehr gute f\u00fcr dieses Problem.)<\/p>\n\n\n\n

    Die Freundesclique<\/strong><\/p>\n\n\n\n

    Ein weiteres Beispiel f\u00fcr ein Problem aus (2) ist das Cliquenproblem. Da geht es um einen Haufen von Sch\u00fclern, die sich m\u00f6gen k\u00f6nnen oder nicht. Eine Clique ist dabei eine Gruppe von Sch\u00fclern, von denen jeder jeden anderen in der Clique mag. Die Aufgabe dazu hei\u00dft: Nenne mir eine solche Clique (wenn es sie denn gibt), in der mindestens vier Sch\u00fcler sind. Hier ist so ein Haufen von Sch\u00fclern:<\/p>\n\n\n\n

    \"\"<\/figure>\n\n\n\n

    Die Buchstaben stehen f\u00fcr die Sch\u00fcler (Anna, Bernd, Charlie, Denise…), die Verbindungen bedeuten, dass die sich m\u00f6gen. Bei einer Handvoll Sch\u00fcler geht das schnell, aber sobal die Zahlen gr\u00f6\u00dfer werden, wird das aufwendiger: der Aufwand steigt n\u00e4mlich exponentiell.
    Die Antwort lautet \u00fcbrigens: ja, es gibt eine 4er-Clique, n\u00e4mlich {A, C, D, F}.<\/p>\n\n\n\n

    Logikr\u00e4tsel<\/strong><\/p>\n\n\n\n

    Auch Logikr\u00e4tsel liegen in diesem Bereich. Damit meine ich beliebige Aufgaben wie<\/p>\n\n\n\n

    \n

    (x oder y) und (nicht (z) oder x)<\/p>\n<\/blockquote>\n\n\n\n

    Dabei sind x, y, z jeweils wahr oder falsch, und die Frage ist: gibt es eine M\u00f6glichkeit, dass diese logische Formel insgesamt wahr ist? Man kann das immer durch Ausprobieren aller M\u00f6glichkeiten \u00fcberpr\u00fcfen, aber bei n Variablen gibt es 2n<\/sup> M\u00f6glichkeiten, der Aufwand steigt exponentiell, und das ist nicht praktikabel.
    Im Beispiel geht das noch, da kann man die 23<\/sup>=8 M\u00f6glichkeiten ausprobieren, und ja, es sind sogar 5 richtige dabei.<\/p>\n\n\n\n

    Zerlegung in Primfaktoren<\/strong><\/p>\n\n\n\n

    Ein viertes Beispiel f\u00fcr ein Problem aus (2) ist die Primfaktorenzerlegung. Bei manchen Verschl\u00fcsselungstechniken nutzt man gerade das aus, dass diese Aufgabe so schwer ist – w\u00e4re sie es nicht, w\u00e4re das nicht sicher. (Zugegeben, ich k\u00fcrze hier etwas ab – die NP-Probleme sind n\u00e4mlich eigentlich Entscheidungsprobleme.)<\/p>\n\n\n\n

    \u00c4hnlichkeit all dieser Aufgaben<\/strong><\/p>\n\n\n\n

    Der Knackpunkt ist jetzt der, dass die verschiedene Aufgaben in (2) sich \u00e4hnlicher sind, als man meint, und das in zweierlei Hinsicht.<\/p>\n\n\n\n