Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten von Spektrum der Wissenschaft 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…
Oktober 2008

Dieser Artikel ist enthalten in Spektrum der Wissenschaft Oktober 2008

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Vielen Dank!