{"id":3652,"date":"2012-03-04T19:04:14","date_gmt":"2012-03-04T18:04:14","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=3652"},"modified":"2023-05-16T08:28:47","modified_gmt":"2023-05-16T06:28:47","slug":"das-p-np-problem-teil-1-was-schwierig-ist","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2012\/03\/das-p-np-problem-teil-1-was-schwierig-ist.htm","title":{"rendered":"Das P-NP-Problem, Teil 1: Was schwierig ist"},"content":{"rendered":"
(10 Kommentare.<\/a>)<\/small> <\/div>\n

Executive summary: Der Schwierigkeitsgrad mancher Aufgaben bleibt bei wachsender Problemgr\u00f6\u00dfe konstant, bei anderen steigt er linear, polynomiell (z.B. quadratisch) oder exponentiell an.<\/em><\/strong><\/p>\n\n\n\n

Die Informatik besch\u00e4ftigt sich unter anderem damit, welche Aufgaben schwierig sind und welche leicht. Es gibt n\u00e4mlich schwierige und leichte Aufgaben. Eine Deutschstunde vorzubereiten, das ist leicht; eine Deutschklausur zu korrigieren, das ist schwer. Oder war das doch umgekehrt? Wie misst man die Schwere von Aufgaben?<\/p>\n\n\n\n

Bei einem g\u00e4ngigen Ansatz in der Informatik (es gibt noch andere) interessiert man sich daf\u00fcr, wie lange man f\u00fcr eine Aufgabe braucht. Das hei\u00dft dann Zeitkomplexit\u00e4t.<\/strong>
Allerdings misst man diese L\u00e4nge nicht in Sekunden oder Minuten oder Jahren, denn wie schnell eine L\u00f6sung gefunden wird, h\u00e4ngt ja auch vom individuellen Arbeitstempo eines Menschen oder eines Computers ab. Stattdessen nimmt man also die Anzahl der dazu n\u00f6tigen Arbeitsschritte als Ma\u00dfeinheit.
Und au\u00dferdem interessiert einen nicht so sehr, wie viele Arbeitsschritte man f\u00fcr eine konkrete Aufgabe braucht (das Durchsuchen eines unsortierten Stapels von zwanzig Deutschklausuren nach der Arbeit eines bestimmten Sch\u00fclers etwa), sondern wie viele Arbeitsschritte man f\u00fcr eine Aufgabe allgemein braucht (das Durchsuchen eines Stapels von Deutschklausuren nach einer Arbeit im Prinzip).<\/p>\n\n\n\n

Wieviel Schritte man f\u00fcr das Durchsuchen eines Stapels von Deutschklausuren im Prinzip braucht, das h\u00e4ngt vor allem von einem ab: der Anzahl der Klausuren. Man braucht mehr Arbeitsschritte, wenn es mehr Klausuren sind. Und zwar ist es immer so, dass man bei einem doppelt so hohen unsortierten Klausurenstapel doppelt so viel Zeit braucht, um eine bestimmte Klausur zu finden. (Das gilt allerdings nur, wenn man nicht dem verbreiteten Glauben anh\u00e4ngt, dass es ohnehin immer die letzte Arbeit ist. Gl\u00fcckskinder k\u00f6nnten nat\u00fcrlich die gesuchte Arbeit immer als erste ziehen, deshalb interessiert uns hier vor allem der durchschnittliche Aufwand bei einer Aufgabe.)<\/p>\n\n\n\n

Und dieser Aufwand – die Anzahl der Arbeitsschritte – w\u00e4chst beim Durchsuchen eines Stapels linear<\/strong>. Das ist ein Fachausdruck f\u00fcr die Erscheinung „doppelt so viel Klausuren machen doppelt so viel Arbeit“ und hei\u00dft so, weil das eine lineare Funktion ist, die als Kurve so aussieht, n\u00e4mlich gar nicht kurvig, sondern gerade:
\"\"
Die x-Achse enth\u00e4lt die wachsende Problemgr\u00f6\u00dfe (die Anzahl der Klausuren), an der y-Achse kann man den Aufwand ablesen. Es gibt absichtlich keine Einheiten, weil die uns ja nicht interessieren.<\/p>\n\n\n\n

Jetzt k\u00f6nnte man argumentieren, das Bearbeiten einer Klausur seien in Wirklichkeit drei Arbeitsschritte, n\u00e4mlich das In-die-Hand-Nehmen, das Lesen des Namens und das Ablegen auf einen Nachbarstapel. Das \u00e4ndert aber nichts an dem Prinzip „doppelt so viel Klausuren machen doppelt so viel Arbeit“, die Kurve ist vielleicht etwas steiler, aber immer noch linear.
Und das gilt ungef\u00e4hr auch noch, wenn man sich zehn Arbeitsschritte daf\u00fcr anrechnet, den Stapel erst einmal aus der Schultasche zu ziehen, unabh\u00e4ngig von dessen Gr\u00f6\u00dfe. Wenn es nur gen\u00fcgend Klausuren sind, spielt so ein einmaliger Zusatzaufwand, egal wie hoch er ist<\/em>, keine gro\u00dfe Rolle mehr. Wir in der Informatik sind da rechnerisch gro\u00dfz\u00fcgig und p\u00e4dagogisch pessimistisch und gehen von beliebig anwachsenden Klassengr\u00f6\u00dfen aus.<\/p>\n\n\n\n

Festgehalten: der Aufwand f\u00fcr das Durchsuchen eines unsortierten Klausurenstapels w\u00e4chst linear (in diesem Fall: zur Anzahl der Klausuren).<\/p>\n\n\n\n

Andere Aufgabenarten sind einfacher. Wenn ich beispielsweise einen Stapel von Deutsch-Sch\u00fclerarbeiten zur Respizienz kriege, dann liegen obenauf zwei Kopien der Aufgabenstellung. Eine davon nehme ich und lege sie zur Seite, um sie – sp\u00e4ter mal – in einen Ordner zu tun. Dieser Aufwand ist f\u00fcr mich konstant,<\/strong> was die Anzahl der Arbeiten betrifft. Die Funktion dazu sieht so aus:
\"\"
Ob man den Aufwand jetzt in einen oder drei oder zehn Arbeitsschritte zerlegt: er bleibt konstant (also unabh\u00e4ngig von der Anzahl der Klausuren).<\/p>\n\n\n\n

Wir haben jetzt also schon Aufgaben mit konstantem Aufwand und welche mit linear wachsendem Aufwand. Der Aufwand kann aber auch noch schneller ansteigen, zum Beispiel beim Sortieren <\/em>von Sch\u00fcleraufs\u00e4tzen. Da ist es n\u00e4mlich so, dass das Sortieren von drei\u00dfig Aufs\u00e4tzen nicht doppelt so viel Arbeit macht wie das Sortieren von f\u00fcnfzehn, sondern mehr als doppelt so viel. (Aber: siehe unten.) Und bei einer Klasse von drei\u00dfig Sch\u00fclern gibt es auch nicht doppelt so viele Chancen f\u00fcr Feindschaften, Tritte, Streit, Tratschereien, sondern mehr als doppelt so viel. Der Aufwand steigt mehr oder weniger quadratisch, und das sieht als Funktion so aus:
\"\"
Beim Sortieren der Arbeiten h\u00e4ngt der Aufwand \u00fcbrigens von der Sortiermethode ab. Nur bei den eher ungeschickten Methoden w\u00e4chst der Aufwand quadratisch, bei anderen Methoden w\u00e4chst er langsamer. Also sind die anderen Methoden in der Praxis sinnvoller. (In Wirklichkeit kommt bei Klausuren auch noch dazu, dass man ja wei\u00df, dass die Arbeit von einer „Alexandra Abel“ wohl recht weit vorne zu liegen kommen wird, und die von „Zacharias Zuser“ ziemlich am Ende, selbst wenn man keine Ahnung hat, wie die Sch\u00fcler in der Klasse sonst hei\u00dfen. Und das erlaubt dann schon wieder noch schnellere Sortierstrategien.)<\/p>\n\n\n\n

Festgehalten: Bei manchen Aufgaben steigt der Aufwand (abh\u00e4ngig von einer Eingangsgr\u00f6\u00dfe) quadratisch. Wir vernachl\u00e4ssigen wie oben schon andere konstante oder linear wachsende Arbeitsschritte, die eventuell noch dazu kommen – wenn die Zahl nur gro\u00df genug ist, l\u00e4uft das auf quadratisch hinaus.<\/p>\n\n\n\n

Ich stelle jetzt noch eine vierte Art von Aufgaben vor, bei der Art von Aufwand noch schneller w\u00e4chst, n\u00e4mlich exponentiell.<\/strong> Schon der quadratisch steigende Aufwand steigt ziemlich steil, aber der exponentiell steigende noch viel mehr, n\u00e4mlich so:
\"\"
Wenn man zum Beispiel eine Zahl in Primfaktoren zerlegen m\u00f6chte, dann steigt der Aufwand exponentiell zur Gr\u00f6\u00dfe der Zahl. (Oder sagen wir: zumindest ist bisher keine bessere L\u00f6sung bekannt als eine mit exponentiell steigendem Aufwand. Wenn mal jemand eine finden sollte, wird der sehr ber\u00fchmt werden.) Exponentielles Wachstum hei\u00dft: wenn eine Zahl x-mal so gro\u00df wird, dann ist der Aufwand f\u00fcr die Primfaktorzerlegung nicht etwa x-mal so gro\u00df (das w\u00e4re lineares Wachstum), und auch nicht x2<\/sup>-mal so gro\u00df (quadratisches Wachstum), sondern etwa 2x<\/sup>-mal so gro\u00df. Das klingt gar nicht so dramatisch, aber erinnern wir uns an die Sache mit den Reisk\u00f6rnern auf dem Schachbrett. Im jeweils einfachsten Fall hat man bei linearem Wachstum am Schluss 64 K\u00f6rner, bei quadratischem Wachstum 4096 K\u00f6rner und bei exponentiellem Wachstum eine Zahl mit zwanzig Stellen.<\/p>\n\n\n\n

Man sieht den Unterschied, wenn man alle vier Funktionen nebeneinander betrachtet:
\"\"
\"\"Jede linear steigende Aufgabe wird irgendwann mal gr\u00f6\u00dfer als jede konstante, jede quadratische \u00fcberholt irgendwann mal die lineare, und die exponentiell steigende Kurve, selbst wenn sie mal langsam anfangen sollte, \u00fcbersteigt irgendwann jede quadratische.<\/p>\n\n\n\n

Wenn die Grafik nur ein bisschen weiter nach rechts gehen w\u00fcrde, dann w\u00e4re die gr\u00fcne Kurve sehr weit oben, und alle anderen, die gelbe eingeschlossen, so weit unten, dass man die Unterschied dazwischen nicht mehr gut erkennen k\u00f6nnte.<\/p>\n\n\n\n

Exponentiell steigt schon sehr steil, aber es gibt nat\u00fcrlich auch noch steileres Wachstum, aber dazu vielleicht sp\u00e4ter mal. (Blogeintrag zur Ackermann-Funktion.<\/a>)<\/p>\n\n\n\n

— Als Zusammenfassung kommen jetzt ein paar mathematischer formulierte Beispiele f\u00fcr Steigungsverhalten. Dabei ist x jeweils die Eingangsgr\u00f6\u00dfe – Anzahl der Klausuren oder was auch immer. Dann ist f(x) der Aufwand in Arbeitsschritten, abh\u00e4ngig von dieser Eingangsgr\u00f6\u00dfe.<\/p>\n\n\n\n

Konstant z.B.:<\/strong>
f(x) = 1
f(x) = 100
(Konstant ist etwa der Aufwand f\u00fcr das Suchen des kleinsten Elements in einer sortierten<\/em> Liste.)<\/p>\n\n\n\n

Linear z.B.:<\/strong>
f(x) = x
f(x) = 3*x
f(x) = 3*x + 100
(Linear w\u00e4chst zum Beispiel der Aufwand f\u00fcr das Suchen in einer unsortierten Liste.)<\/p>\n\n\n\n

Quadratisch z.B.:<\/strong>
f(x) = x2<\/sup>
f(x) = x2<\/sup> + 100
f(x) = x2<\/sup> + 3*x + 100
(Quadratisch w\u00e4chst zum Beispiel der Aufwand f\u00fcr das Sortieren einer Liste, wenn man mit einem nicht besonders guten Sortierverfahren arbeitet.)<\/p>\n\n\n\n

Polynomiell* z.B.:<\/strong>
f(x) = x4<\/sup>
f(x) = x4<\/sup> + x3<\/sup>
f(x) = x4<\/sup> + x3<\/sup> + x2<\/sup> + 3000*x + 9000<\/p>\n\n\n\n

Exponentiell z.B.:<\/strong>
f(x) = 2x<\/sup>
f(x) = 20x<\/sup>
f(x) = 2x<\/sup> + x4<\/sup> + x3<\/sup> + x2<\/sup> + 3000*x + 9000
(Exponentiell w\u00e4chst zum Beispiel der Aufwand bei der Primfaktorzerlegung.)<\/p>\n\n\n\n

*Polynomiell ist eine Art \u00dcberbegriff zu quadratisch: x2<\/sup> ist polynomiell, und x3<\/sup> auch und x5<\/sup> auch und so weiter – also immer dann, wenn es um xirgendwasgr\u00f6\u00dfer1<\/sup> geht. Das kann quadratisch sein oder nicht, mit der dem Informatiker eigenen Gro\u00dfz\u00fcgigkeit sagen wir polynomiell dazu und gut ist.<\/p>\n\n\n\n

(Fortsetzung folgt.<\/a>)<\/p>\n","protected":false},"excerpt":{"rendered":"

(10 Kommentare.) Executive summary: Der Schwierigkeitsgrad mancher Aufgaben bleibt bei wachsender Problemgr\u00f6\u00dfe konstant, bei anderen steigt er linear, polynomiell (z.B. quadratisch) oder exponentiell an. Die Informatik besch\u00e4ftigt sich unter anderem damit, welche Aufgaben schwierig sind und welche leicht. Es gibt n\u00e4mlich schwierige und leichte Aufgaben. Eine Deutschstunde vorzubereiten, das ist leicht; eine Deutschklausur zu korrigieren, […]<\/p>\n","protected":false},"author":2,"featured_media":3683,"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-3652","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_alle2_klein.jpg","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/3652","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=3652"}],"version-history":[{"count":2,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/3652\/revisions"}],"predecessor-version":[{"id":56688,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/3652\/revisions\/56688"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media\/3683"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=3652"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=3652"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=3652"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}