Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.
Serie Mathematik (Teil IIa): Das Komplexitätsproblem: Wie man einen Brief frankiert
Im zweiten Teil der Serie geht es um Komplexität, hier um die Frage, wie effizient sich bestimmte kombinatorische Probleme lösen lassen. In der Komplexitätstheorie ist dies unter dem Kürzel "P = NP" bekannt. Für die Lösung bietet das Clay Institute ein Preisgeld von einer Million Dollar.
Eines Tages muss sich ein früher babylonischer Schreiber entschlossen haben, seinen Schülern Arithmetik beizubringen. Er stellte ihnen Probleme der Art "Ich fand einen Stein, habe ihn aber nicht gewogen ...". Seitdem interessieren sich Mathematiker stets auch für die verborgenen Tiefen scheinbarer Alltagsprobleme: wie man Torten in Teile schneidet, Knoten knüpft oder Münzen rotieren lässt. Aber selbst die Fachleute waren davon überrascht, welch abgründiges Geheimnis hinter einer unschuldigen Frage zu Briefmarken steckt.
Angenommen, Ihr Postamt verkauft Ihnen Briefmarken nur in zwei Stückelungen: zwei Cent und fünf Cent. Kombiniert man diese Werte, dann lässt sich daraus fast jeder gewünschte Wert zusammensetzen. Wenn beispielsweise ein Brief neun Cent kostet, dann kann man eine Briefmarke mit fünf Cent und dazu zwei mit je zwei Cent daraufkleben. Nicht darstellen lassen sich ein Cent und drei Cent – und das sind die einzigen nicht darstellbaren Beträge. Jeden geraden Betrag erreicht man jedenfalls mit ausreichend vielen Zwei-Cent-Marken – zumindest, falls der Umschlag groß genug ist –, und jeder ungerade Betrag über fünf Cent ergibt sich mit Hilfe einer Fünf-Cent- und entsprechend vielen Zwei-Cent-Marken...
Angenommen, Ihr Postamt verkauft Ihnen Briefmarken nur in zwei Stückelungen: zwei Cent und fünf Cent. Kombiniert man diese Werte, dann lässt sich daraus fast jeder gewünschte Wert zusammensetzen. Wenn beispielsweise ein Brief neun Cent kostet, dann kann man eine Briefmarke mit fünf Cent und dazu zwei mit je zwei Cent daraufkleben. Nicht darstellen lassen sich ein Cent und drei Cent – und das sind die einzigen nicht darstellbaren Beträge. Jeden geraden Betrag erreicht man jedenfalls mit ausreichend vielen Zwei-Cent-Marken – zumindest, falls der Umschlag groß genug ist –, und jeder ungerade Betrag über fünf Cent ergibt sich mit Hilfe einer Fünf-Cent- und entsprechend vielen Zwei-Cent-Marken...
Schreiben Sie uns!
Beitrag schreiben