« vorheriger Beitrag  · nächster Beitrag »

30.11.09 · 08:14 Uhr

Komplexitätsklassen als mathematische Axiome

Kategorie: Technik

Michael Freedman schlägt vor, komplexitäts-theoretische Vermutungen als zusätzliche Axiome zur üblichen ZF-Mengenlehre zu postulieren. Als Anwendung beweist er eine Ungleichung für die Weite von Knoten.

Der Artikel "Complexity classes as mathematical axioms" erscheint in der aktuellen Ausgabe der "Annals of Mathematics" und kann hier heruntergeladen werden.

Bekanntlich startet man in der Mathematik immer von Axiomen, aus denen sich alle Theoreme herleiten lassen müssen.
Allgemein anerkannte axiomatische Grundlage der Mathematik ist die Zermelo-Fraenkel-Mengenlehre ZF. In der Regel nimmt man zur Zermelo-Fraenkel-Mengenlehre noch das Auswahlaxiom hinzu, ohne das sich viele mathematische Sätze nicht beweisen lassen. Die so gegebene Theorie (ZF und Auswahlaxiom) nennt man ZFC. (Cohen hat 1963 gezeigt, daß das Auswahlaxiom aus den ZF-Axiomen nicht bewiesen werden kann, und schon seit Gödel wußte man, daß sich die Widerspruchsfreiheit von ZFC nicht beweisen läßt, aber das ist ein anderes Thema.)

In der Komplexitätstheorie von Algorithmen gibt es grundlegende offene Fragen (wie das P=NP-Problem, auf dessen Lösung das Clay-Institut ein Preisgeld von 1 Million Dollar ausgesetzt hat), die seit Jahrzehnten offen sind und bei denen man sich fragt, ob sie vielleicht innerhalb ZFC weder bewiesen noch widerlegt werden können.

Der Topologe Michael Freedman (bekannt unter anderem für den Beweis der 4-dimensionalen Poincare-Vermutung 1981) schlägt nun vor, solche komplexitäts-theoretischen Vermutungen als zusätzliche Axiome zu den ZF-Axiomen hinzuzunehmen und zu schauen, welche Folgerungen in der Mathematik (außerhalb der Komplexitätstheorie) sich aus diesen zusätzlichen Axiomen ergeben würden.

Diesen Vorschlag untermauert er im neuesten Heft der "Annals of Mathematics" mit einem konkreten Beispiel: er leitet eine Ungleichung für bestimmte Knoten-Invarianten aus einem komplexitäts-theoretischen Axiom her.

Das von Freedman benutzte komplexitäts-theoretische Axiom ist nicht die bekannte P-NP-Vermutung, sondern die etwas komplizierter zu formulierende NP -P^#P-Vermutung. Zur Erklärung der Begriffe:
- P bezeichnet Entscheidungsprobleme, die sich (auf einer Turing-Maschine) in polynomieller Zeit entscheiden lassen
- NP bezeichnet Probleme, für die es einen Algorithmus in polynomieller Zeit gibt, der eine gegebene positive Antwort bestätigen könnte
- #P bezeichnet Probleme, für die es einen Algorithmus in polynomieller Zeit gibt, der für eine gegebene Menge von Eingaben überprüft, wieviele zu einer positiven Antwort führen
- P^#P bezeichnet Probleme, die sich durch Rechnungen in polynomieller Zeit und zusätzlicher Befragung des #P-Orakels lösen lassen.

Freedman geht nun von dem "Axiom" aus, daß es Probleme in P^#P gibt, die nicht zu NP gehören. Aus diesem Axiom leitet er ein Theorem über Knoten ab, das bisher nicht bekannt war - eine (relativ kompliziert zu formulierende) Ungleichung für eine elementare Knoteninvariante, die Weite des Knotens. (Ich hoffe mal, 'Weite' ist die korrekte Übersetzung von 'girth'.)

Sein Argument baut auf der Dissertation von Vertigan auf, der 1991 bewiesen hatte, daß Berechnungen spezieller Werte des Jones-Polynoms von Knoten ein #P-schweres Problem ist (d.h. dieses Problem gehört nicht zur Klasse #P).

Die Ungleichung, die er beweist, betrifft die Weite eines Knotens. Zur Erklärung: ein Knoten ist ein (verknoteter) Kreis in unserem Anschauungsraum R³. Einen Knoten im R³ kann man auf verschiedene Ebenen projizieren, die entstehenden Bilder nennt man Diagramme des Knotens. Für ein solches Knotendiagramm D in der Ebene definiert man die 'Weite' als die maximale Anzahl von Schnittpunkten mit einer horizontalen Gerade: g(D)=max(#{D ∩ {y=c}}: c in R), Die 'Weite' des Knotens K ist dann die minimale Weite der Diagramme einer Projektion dieses Knotens: g(K)=min(g(D): D Diagramm von K).

Ein Knoten-Diagramm D mit g(D)=8.
Der abgebildete Knoten ist eigentlich unverknotet, es gibt andere Diagramme mit g(D)=2.

Freedman beweist nun (m.H. seines Axioms) einen Satz, der (unter einer technischen, möglicherweise immer erfüllten, Voraussetzung an die Dehn-Chirurgien des Knotens) eine Ungleichung zwischen der 'Weite' eines Knotens und der Anzahl von Kreuzungspunkten und lokalen Extrema seiner Knotendiagramme gibt.

Aus der Einleitung des Artikels:

We assume a technical but well accepted separation "axiom" NP < P^#P, which we call Axiom A, and prove a theorem, Theorem A, in knot theory. The theorem is easily and briefly expressed in terms of classical notions such as "girth" and "Dehn surgery" and appears to be as close to current research topics in knot theory [...] Theorem A is extremely believable but seems to exist in a "technique vacuum". What makes the theorem interesting is that it sounds both "very plausible" and "impossible to prove".

M. Freedman (2009). Complexity Classes as Mathematical Axioms Annals of Mathematics (2), 170 (2), 995-1002 arXiv: 0810.0033v4

 

Autor: Thilo· 0 Kommentare· Permalink· Trackback-URL

Tags: algorithmen· axiome· beweis· chirurgie· entscheidung· knoten· komplexität· logik· topologie· ungleichung· weite