20.11.2006

Numb3rs – 1×02 – Uncertainty Principle

Posted in Sneak Review at 13:18 by Fuzz

In dieser Folge werden Banküberfälle mit dem Uncertainty Principle (besser bekannt unter dem Heisenbergsche Unschärferelation) verknüpft. Dieses – auf den Alltag übertragen – besagt, dass sich ein Experiment alleine durch die Beobachtung verändert. (Die Details der restlichen Quantenphysik lasse ich mal mal ganz galant unter den Tisch fallen. Vielleicht schreibt Starkiller dazu was?)

David hat mit Hilfe seiner Formeln Ort und Zeit berechnet, wann die Bankräuber das nächste Mal zuschlagen werden. Die haben schon einen Haufen Überfälle hinter sich und liefern so genügend Zahlenmaterial für eine Vorhersage. Die Bankräuber werden als die “Charm School Boys” bezeichnet, weil sie immer höflich, nett, zuvorkommend und unbewaffnet sind.

Beim Zugriff von Rob und seinem Team geht aber alles schief. Die zwei netten Jungs haben noch 4 andere Typen als Verstärkung dabei, die bis jetzt immer unauffällig im Hintergrund geblieben sind und nun heftige Gegenwehr liefern. Insgesamt werden 3 bei der Schiesserei getötet und dafür fühlt sich Davin verantwortlich. Er entwickelt darauf eine Art mathematische Neurose und versucht krampfthaft P=NP zu beweisen oder zu wiederlegen.

P=NP? WTF? Das ist total einfach. In der Mathematik gibt es Dinge, die sich in polynomiell beschränkter Zeit lösen lassen. WTF? Ein Beispiel? Wenn ich die Bücher meines Regals nach Five Rooms durchsuchen will (nicht zu verwechseln mit Four Rooms) und in meinem Regal stehen 200 DVDs (schön wär’s), dann bräuchte ich dafür 200 (Zeit-)Einheiten. Wenn ich 2 Buchregale mit 400 DVDs hätte, dann bräuchte ich 400 Einheiten. Der Mathematiker sagt dazu schlicht und ergreifend, dass die Komplexität dieses Problems O(n) ist (sprich: O von n). Und damit ich sicher gehen kann, dass ich den Film nicht übersehen habe, durchsuche ich das Buchregal nochmal und die Komplexität ist dann O(2n). Das ist natürlich falsch, weil Mathematiker die 2 einfach unter den Tisch fallen lassen. Die Zeit durch das Durchsuchen steigt also proportional mit der Anzahl meiner DVDs. Doppelte Anzahl von DVDs, doppelter Zeitaufwand. Das dürfte sogar einem Atze einleuchten.

Und wenn ich meine DVDs nun sortieren will? Das ist auch ganz einfach. Ich schmeisse meine 200 DVDs auf den Boden und durchsuche sie nach dem alphabetisch ersten Titel. Also das ist A For Andromeda, diesen stelle ich an Position 1 ins Regal und suche nun den Titel, der dann folgt. Das ist American Dad! Wieder ins Regal stellen, Rest durchsuchen, A-Team finden usw… usw… und irgendwann komme ich bei Zorro and Son an. Wie lange dauert nun das? Ich habe zwei geschachtelte Schleifen, also n*n (n CDs liegen auf dem Boden und müssen durchsucht werden und das muss ich n mal machen), in Mathesprech ist das O(n^2). Was haben O(n) und O(n^2) und O(n^124) gemeinsam? Es sind Polynome. Dagegen kann man sich nicht nicht impfen, das ist die Bezeichnung für solche einfache Formeln, die Mathematiker schon lösen, noch während sie unter der Dusche stehen. Alle Probleme, deren Lösungszeit mit Hilfe einer polynomieller Funktion ausgedrückt werden kann (egal ob n, n^2 oder auch 3*n^3 + 2*n^2 + 47), gehören in die Klasse P.

Und NP sind dann die anderen Probleme, die sich nicht in polynomieller Zeit lösen lassen. Die gibt es auch.

(Soll ich nun das abgelutschtes Beispiel 1 oder abgelutschtes Beispiel 2 bringen?) Ich entscheide mich mal nicht den Handlungsreisenden, sondern für das Rucksackproblem. Angenommen du hast einen Rucksack mit einem bestimmten Fassungsvermögen, welches nicht überschritten werden darf. Und du hast 10 Gegenstände, von denen du möglichst viele mitnehmen möchtest, weißt aber nicht welche. Sture Mathematiker (und Informatiker) gehen dann einfach jede Kombination durch. Wieviele gibt es? Nunja, jeder Gegenständ kann entweder mitgenommen oder nicht. Das macht pro Gegenstand 2 Möglichkeiten. Und wir haben 10 Gegenstände bzw. einfach mal n. Also haben wir 2^n Möglichkeiten. Bei 10 Gegenstände wären das schon 1024 (=2^10) Möglichkeiten. In Mathesprech ist das O(2^n). Das ist ein NP Problem, weil die 2^n eben kein Polynom ist. Blöd.

P-Probleme sind (in der Regel) viel schneller zu lösen als NP-Probleme und deshalb haben die beiden Klassen von den Mathematikern auch zwei verschiedene Namen bekommen.

Quote des Wiki-Artikels P=NP:

P ist eine Teilmenge von NP, denn die Probleme aus P lassen sich ebenfalls nichtdeterministisch in Polynomialzeit lösen. Unklar ist aber, ob NP ebenfalls eine Teilmenge von P ist, also ob die beiden Klassen identisch sind.

Der umgekehrte Beweis P<>NP würde aber auch zu gleichem Ruhm führen. Wer die Lösung weiß, bitte per Mail an mich. Aber mal im Ernst: Sollte jemand diesen Beweis führen können, wäre ihm ein Name in der Mathematik sicher, zumal das P=NP-Problem eines der 10 Millennium-Probleme ist, für dessen Lösung es jeweils 1 Million Dollar gibt. Natürlich auch Ruhm und Ehre für die Ewigkeit. Be a famous math geek.

Zurück zur Serie.

Die Schiesserei war für eine Serie ganz schön gut inszeniert, da kamen direkt warme Erinnerungen an Heat hoch.

Der mathematische Aspekt trat in dieser Folge schon etwas (mehr) in den Hintergrund, zumal es sich bei der HU um ein physikalisches Gesetz handelt.

Ganz nett und durchaus guckbar.

Schlagwörter: Guckbar, n=np, numb3rs

Permalink