Mathe-Vermutung bewiesen - Hilfsformel eine Million A4-Seiten lang

25. Jänner 2011, 10:27

Linzer Wissenschafter schafften mit Computer Beweis, an dem Mathematiker 30 Jahre lang scheiterten

Mathematiker stellen sich manchmal für den Laien recht seltsam anmutende Aufgaben. "Planare Partitionen" nennt sich eine davon, bei der es um die Berechnung von Würfeln geht, die nach bestimmten Regeln angeordnet werden müssen. Linzer Forscher haben nun eine 1983 von zwei US-Mathematikern aufgestellte mathematische Vermutung über solche "planare Partitionen" bewiesen. Dies gelang ihnen ausschließlich mit dem Computer, der dafür Monate rechnen musste, und unter Verwendung einer Hilfsformel, die ausgedruckt rund eine Million A4-Seiten umfassen würde. Die Arbeit der Wissenschafter wurde nun in der Fachzeitschrift PNAS veröffentlicht - auf lediglich vier Seiten.

Fixe Regeln

Bei einer "planaren Partition" werden auf einer schachbrettartigen Grundfläche aus würfelförmigen Bauklötzen Türme gebaut, und zwar nach fixen Regeln: Kein Turm darf höher sein als die Länge der Grundfläche und auch nicht höher als ein Turm dahinter oder links davon. Die Mathematiker interessiert nun, wie viele verschiedene Anordnungen sich auf einer bestimmten Grundfläche bauen lassen. Ohne weitere Regeln ist das relativ einfach, schwieriger wird es allerdings, wenn die Anordnung bestimmte Symmetrien aufweisen soll oder andere Vorgaben gemacht werden.

Für eine spezielle Vorgabe, die "total symmetrischen planaren Partitionen", haben schon 1983 George Andrews und David Robbins eine Vermutung für eine allgemeingültige Formel für beliebige Größen vorgelegt. "Das war aber nur eine Vermutung, die fast 30 Jahre unbewiesen geblieben ist", erklärte Manuel Kauers vom Institut für Symbolisches Rechnen der Uni Linz im Gespräch mit der APA. Gemeinsam mit seinem Linzer Kollegen Christoph Koutschan und den US-Mathematiker Doron Zeilberger hat es Kauers in dem vom Wissenschaftsfonds FWF geförderten Projekt nun geschafft, die Vermutung zu beweisen.

"Nur ein paar Monate"

Koutschan hat dabei die zur Berechnung des Beweises notwendigen Programme so optimiert, dass die Rechenzeit in Summe "nur ein paar Monate dauerte. Wenn man das so macht wie im Lehrbuch, dann würde das Hunderte von Jahre dauern", so Kauers.

Aber nicht nur die Rechenzeit ist beeindruckend. Für die Beweisführung war es notwendig, den Computer eine Hilfsgleichung berechnen zu lassen. Während die zu beweisende Gleichung "ganz klein ist, das ist nur eine Zeile", so Kauers, ist die Hilfsgleichung für den Beweis deutlich komplexer: Ausgedruckt würde sie rund eine Million A4-Seiten umfassen.

Mit dem vom Computer berechneten Beweisverfahren konnten die Wissenschafter auch zeigen, dass Programme durchaus mathematische Probleme knacken, an denen Mathematiker scheitern. Zumindest für einen gewissen Typ von Problemen liege die Zukunft der Mathematik sicher im Computer, ist Kauers überzeugt. (APA)

Der WebStandard auf Facebook

Share if you care
16 Postings
Meine Vermutung bzgl. der 1 Million A4 - Seiten:

Früher (Computer - Steinzeit bis Computer - Spätmittelalter, also früher Pentium - Zeit) war es üblich, 2 KB als 1 DIN A4 - Seite anzugeben.

Sozusagen für das zeitgenössische Äquivalent zum heutigen "Internetausdrucker".

Vielleicht war ja einer der beteiligten Wissenschaftler der Meinung, daß es heute noch Leute gibt, die diese Meldung interessieren würde und denen ein simples "naja, die Berechnung hat halt 2 GB RAM gebraucht" nichts sagen würde.

Meine Vermutung ist, daß der Sager im Original lautete:

"Für den Algorithmus, so nennen wir die Formel, benötigten wir soviel Speicherplatz, wie für eine Million DIN A4 - Seiten."

Dazu ein bisserl "Stille Post" und wir haben den Salat.

Frage in Bezug auf das Gebiet der theoretischen Informatik:

Ein Algorithmus generiert eine riesige Formel, die Teil eines Beweises sein soll, den wahrscheinlich nie ein Mensch verifizieren wird können.
Somit verlagert man die Beweislast auf die Notwendigkeit, die Korrektheit des Algorithmus beweisen zu müssen.
Bei bisherigen theoretischen Beweisen von Algorithmen ist im Allgemeinen nach einer Schleife und ein paar Verzweigungen Schluß.
Wie kann man also zeigen, daß die Hilfsformel stimmt ?

Es könnte schon sein,

dass durch die gestaltung des algorithmus' ein induktiver beweis möglich ist ... Aber wissen tu ichs natürlich nicht ...

Ausgedruckt würde sie rund eine Million A4-Seiten umfassen.

*hehe* Das erinnert mich aber an diese Simpsons Folge. Moe frägt Barney, ober es sich noch daran erinnern könne, dass er mal erwähnt hat, er müsse seine Getränkeliste zur Auswertung der NASA schicken. Barney kann sich erinnern und meint, dass alle herzlich über den Scherz gelacht hatten. Moe holt eben diese Ausdrucke herbei und sagt: Das war kein Scherz, ich habe das Ergebnis heute bekommen :-)

"Mit dem vom Computer berechneten Beweisverfahren konnten die Wissenschafter auch zeigen, dass Programme durchaus mathematische Probleme knacken, an denen Mathematiker scheitern. Zumindest für einen gewissen Typ von Problemen liege die Zukunft der Mathematik sicher im Computer, ist Kauers überzeugt."

Autor hat wohl keine Ahnung. Das 4-Farb-Problem wurde schon 1976 per Computerprogramm gelöst.

Danke Standard

.. ich kenne mich durch mein Mathestudium ziemlich gut in Mathematik aus.

Trotzdem kann ich bei dem Text hier nur raten, wo das eigentliche Problem liegen könnte.
Gib mir bitte ein grünes Stricherl, wenn du auch eine genauere (mathematisch exakte) Beschreibung gewollt hättest.

wtf?

1 mio a4-seiten?

schriftgrösse, zeilenhöhe, zeilenabstand, schriftweite, rahmen, fuss- und kopfzeilen.

was soll das für eine grösse sein 'a4-seite'?

times new roman, schriftgröße 12, was windows halt benutzt;)

Die Formel klingt nach einem Copy/Paste Massaker.

welche arme sau...

..hat die formel eingetippt?

"Für die Beweisführung war es notwendig, den Computer eine Hilfsgleichung berechnen zu lassen."

haben wir auch den ganzen text gelesen? wir reden von der hilfsgleichung, weil die eigentlich gleichung nur 1-2 zeilen lang ist !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

mit dem gewissen Typ meint er wohl Kombinatorik und/oder logische Kalküle

6 Millionen $ollar liegen noch auf der Straße...

...also: Auf geht's:

http://de.wikipedia.org/wiki/Unge... Mathematik

Have fun.

Ich habe wahrhaft wunderbare Lösungen für diese Probleme gefunden, aber der dieses Posting hier ist zu schmal, um sie zu fassen.

Die Kommentare von Usern und Userinnen geben nicht notwendigerweise die Meinung der Redaktion wieder. Die Redaktion behält sich vor, Kommentare, welche straf- oder zivilrechtliche Normen verletzen, den guten Sitten widersprechen oder sonst dem Ansehen des Mediums zuwiderlaufen (siehe ausführliche Forenregeln), zu entfernen. Der/Die Benutzer/in kann diesfalls keine Ansprüche stellen. Weiters behält sich die derStandard.at GmbH vor, Schadenersatzansprüche geltend zu machen und strafrechtlich relevante Tatbestände zur Anzeige zu bringen.