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.
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


Ian Stewart ist Mathematiker, Buchautor und Wissenschaftsjournalist. Er unterrichtet als Professor
an der University of Warwick in England. Sein letztes Buch schildert "Die wunderbare Welt der Mathematik" (Piper-Verlag, München 2007).
abrufen





RELATIV EINFACH |
Go for Launch |
WILD DUECK BLOG |
Gute Geschäfte |
Anatomisches Allerlei |
Umweltforsch |
Himmelslichter |
Robotergesetze |
Natur des Glaubens |
Fischblog |
Mente et Malleo | 





