Aus ProgrammingWiki
Autoren:
- Ragna-Diana Steglich (sirasteg@stud.hs-zigr.de)
- Elisabeth Vogel (sielvoge@stud.hs-zigr.de)
Motivation
Bis zur heutigen Zeit sind in der Mathematik sieben bisher unlösbare Probleme entdeckt und formuliert worden: Die sogenannten Millennium Probleme. Im Jahr 2000 wurde vom Clay Mathematics Institute in Cambridge eine festgestezte Liste mit diesen sieben Problemen erstellt und zusätzlich vom Institut in Massachusetts ein Preisgeld von einer Million US-Dollar auf jede Lösung für eines dieser Probleme ausgesetzt.
Mit einem dieser Millennium Probleme wollen wir uns hier genauer beschäftigen: mit dem 
-
-Problem. Im Folgendem soll geklärt werden, was und eigentlich ist, worin das eigentliche Problem besteht und was man tun muss, um vielleicht um eine Million US-Dollar reicher zu werden.
Selbstverständlich besteht das Hauptinteresse darin, dieses Problem aus der Sicht der Informatik zu beleuchten, denn auch da erfreut es sich großer Aufmerksamkeit. Vorreiter, das --Problem betreffend, sind unter anderem der ukrainische Informatiker Leonid Levin und der Professor für Informatik an der University of Toronto Stephen Arthur Cook. Außerdem kann man noch den britischen Mathematiker und Logiker Frank Plumpton Ramsey nennen, der eines der schwerste Probleme dieses Themenbereiches erkannt hat.
Es ist von aller größter Wichtigkeit von einzelnen kleinen Problemen Abstand zu nehmen und die Vielfalt an Herausforderungen in bestimmte Klassifikationen zu unterteilen. Für die eine Klasse ist es dann möglich die Lösung für ein Problem schnell und mit höchster Effizienz zu erreichen. Für die andere Klasse ist das Finden einer Lösung ein Ding der Unmöglichkeit aber mit der Hilfe einer kleinen Fee (Nichtdeterminismus), die einem eine Lösung verrät, ist es wenigstens noch im Bereich des möglichen diese Lösung auf ihre Richtigkeit hin zu überprüfen.
Es soll auch untersucht werden, welchen Einfluss das --Problem auf die eine oder andere Verschlüsselungmechanik hat und auch welche die schwersten der schweren Probleme sind.
Komplexitätsklassen
In den meisten Fällen ist es sehr schwierig zu entscheiden, ob ein Problem einfach oder nur sehr schwer lösbar ist. Es ist zum Beispiel ohne weiteres möglich, dass Probleme, die sich formulierungstechnisch nur sehr gering unterscheiden, vollkommen unterschiedliche Aufwände zu ihrer Lösung verlangen. Die folgende Tabelle kann dies verdeutlichen:
Für das --Problem ist es von Vorteil die Komplexitätsklassen 
und 
genauer zu untersuchen, wobei 
und 
im Vordergrund stehen werden.
Die Probleme, die mehr oder weniger leicht und informell effizient lösbar sind, schreibt man der Komplexitätsklasse zu. definiert die Probleme, für die eine Lösung in polynomialer Zeit einfach zu verfizieren ist. Ferner kann die Klasse als eine Art "Überklasse" bezeichnet werden, denn es gilt 
. Leider ist aber noch unbekannt ob 
oder 
ist. Untereinander verhalten sich die Komplexitätsklassen und ähnlich undurchsichtig, denn es ist noch nicht geklärt, ob 
oder 
gilt, wobei nur die wenigsten Forscher an glauben. Die folgende Grafik illustriert die mögliche Verbindung der Klassen untereinander:
Klasse P
- Definition
- ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.
Der Klasse , manchmal findet sich auch die Bezeichnung 
, werden also Probleme der Größe 
(Eingabewort) zugeordnet, für deren Lösung der Aufwand im worst-case durch ein Polynom in nach oben beschränkt werden kann. Das Polynom besitzt dann die Größe der Eingabe. Abstrakter gesagt umfasst die Klasse Entscheidungsprobleme die in Polynomzeit für deterministische TURING-Maschinen lösbar sind. Allgemein wird diese Komplexitätsklasse auch als Klasse der "praktisch lösbaren" Probleme betrachtet.
Algorithmen, deren Komplexität nicht durch Polynome beschränkt werden können sind ineffizient, das heißt, dass der Aufwand mit der Anzahl der Eingaben exponentiell nach oben steigt. Daraus ergibt sich die unumgängliche Tatsache, dass diese Algorithmen die Rechenkapazität jedes irdischen Computers irgendwann bei weitem sprengen würden.
Nachgewiesenermaßen existieren (berechenbare) Probleme, die nicht in der Klasse enthalten sind. Mit Hilfe verschiedener Diagonalisierungstechniken und Zeithierachiesätzen ist es möglich diese Probleme ausfindig zu machen. Es ist bekannt, dass diese Probleme nur mit exponentiellem oder meistens auch mehrfach exponentiellem Aufwand lösbar sind. Probleme mit dieser Eigenschaft werden mit bezeichnet. Es ist vollständig bewiesen, dass folgendes gilt: .
Klasse NP
- Definition
-
- Die Klasse der -Probleme ist die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können.
Wie die Definition schon sagt, handelt es sich bei den -Problemen um die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können. Die Überprüfung der Lösung erfolgt in Polynomzeit. Diese Probleme umfassen eine Teilmenge von und umschließen eine sehr große Palette relevanter Probleme.
Wie bereits aus der Definition der Klasse bekannt ist, sind Probleme in deterministisch in Polynomzeit berechenbar. Dies bestätigt die Theorie, das eine Teilmenge von ist. Genau an diesem Punkt beginnt das eigentliche --Problem, denn es ist nicht klar, ob die beiden Klassen vollkommen identisch sind oder ob nur eine Teilmenge von ist. Identisch heißt, dass selbst die schwersten Probleme aus genauso effizient berechenbar und vor allem lösbar sind, wie jene aus .
Es steht fest, dass jedes Problem aus auch in liegt. Daher gilt: 
. Ein Nachweis dafür könnte die Vorstellung der Arbeitsweise einer nichtdeterministischen TURING-Maschine sein. Der "Ratevorgang" wird durch die (deterministische) Berechnung der Lösung ersetzt und die Verifikation findet sowieso in polynomialer Zeit statt.
Bis heute ist es niemandem gelungen zu zeigen, dass Probleme nachgewiesenermaßen zu aber nicht zu gehören. Noch völlig im Dunkeln liegt auch die Frage, ob 
oder ist, wobei fast kein Forscher daran glaubt, dass gilt.
Reduktion
Die Reduktion an sich stellt eine Grundlage des -Vollständigkeitsbeweises dar. Es soll gezeigt werden, dass ein Problem nicht "härter" ist, als ein anderes. Gegeben sei daher ein Entscheidungsproblem 
, dass in polynomialer Zeit zu lösen ist. Ferner gibt es die Annahme, dass ein weiteres Problem 
existiert, für das die Lösung in der Zeit 
bekannt ist. 
sei eine Instanz von 
und 
stellt die Instanz von 
dar. Nun wird jede beliebige Instanz in eine beliebige Instanz überführt. Die Transformation von nach erfolgt selbstverständlich in polynomialer Zeit.
Polynomiale Reduktion
Grafische Darstellung der polynomialen Reduktion
Es besteht aber nun die Intention darin, die polynomiale Reduktion in den Vordergrund zu stellen. Trotzdem sich die Suche nach einer Antwort auf die Frage 
mehr oder weniger im Kreis dreht, ist es dennoch gelungen einen Schritt voran zu kommen. Mit der 
-Vollständigkeit scheint man nun endlich in die richtige Richtung zu blicken.
- Polynomiale Reduktion wird wie folgt definiert!
- Seien und Sprachen (Probleme) mit
und 
. Dann heißt polynomial reduzierbar auf 
, geschrieben: 
, wenn es eine totale und mit polynomialer Komplexität berechenbare Funktion 
gibt, sodass für alle 
gilt: 
.
Es könnte nun zu einigen Unstimmigkeiten und Fehlinterpretationen mit dem gewählten Symbol für die Relation polynomial reduzierbar kommen: 
. Mit diesem Symbol soll die Idee des Schwierigkeitsgrades hervorgehoben werden:
- " ist im Wesentlichen nicht schwieriger als ."
- oder
- " ist mindestens so schwierig wie ."
Anders ausgedrückt: Schafft man es das Problem zu lösen, dass vielleicht nur etwas schwieriger als ist, dann benötigt man für die Lösung von einen nur geringfügig größeren Zeitaufwand. Das Zeichen für die polynomiale Reduktion darf auf keinen Fall als "etwas kleiner machen" fehlinterpretiert werden, da sich in diesem Fall fatale Denkfehler bei der Durchführung von Reduktionen einschleichen können, die unter Umständen dann ein falsches Ergebnis zur Folge haben. Die Grafik stellt optisch eine Reduktion dar und unterstreich die Verhältnisse zwischen den Problemen und und der zur polynomialen Reduktion "vorgeschalteten" Funktion 
.
Aus dem bereits zusammengetragenen Wissen über die Komplexitätsklassen und der oben durchgeführten Definition des Symbols: , lassen sich nun folgende Sätze ableiten:
- 1. Satz: Wenn
und 
, dann gilt 
.
- 2. Satz: Wenn und
, dann gilt 
.
- 3. Satz: Wenn und
, dann gilt 
.
Letzter Satz zeigt, dass es unter gewissen Umständen und Vorraussetzungen keinen Polynomzeitalgorithmus gibt.
NP-Vollständigkeit
NP-schwere Probleme
- Definition
-
- Ein Problem (eine Sprache) heißt -schwer, wenn für alle Probleme (Sprachen)
gilt: 
.
Zu aller erst ist es wichtig zu wissen, dass ein -schweres Problem nicht unbedingt in liegen muss. Dies scheint zunächst ein Paradoxon zu sein.
Nach der Definition ist also ein Problem genau dann -schwer, wenn für alle Probleme 
aus der Klasse gilt, dass diese auf polynomial reduzierbar sind. Da stellt sich unweigerlich die Frage, wie man denn nun für das Problem beweisen soll, dass alle NP-Probleme auf polynomial reduzierbar sind. Da das Zeichen transitiv ist, ist es möglich eine Vereinfachung für diese Problemstellung zu finden. Diese kann Anwendung finden, wenn mindestens ein bekanntes -schweres Problem 
vorhanden ist. In diesem Fall ist es nur nötig zu beweisen, dass das Problem auf reduzierbar ist. Durch die Transitivität von heißt es dann: für alle 
. Die folgende Illustration zeigt diesen Sachverhalt.
NP-vollständige Probleme
- Definition
-
heißt -vollständig, wenn -schwer ist und 
gilt.
Die Grafik zeigt die vermutliche Relation der Problemklassen in einem VENN-Diagramm unter der Annahme, dass ist. 
bedeutet hier die Klasse der -schweren Probleme und 
ist die Klasse der -vollständigen Probleme. Noch ist nicht bekannt ob 
und ob 
. Aber da 
, gilt 
oder 
oder aber auch beide Beziehungen. Die meisten Forscher glauben aber an: 
. Da aber die Wissenschaft keine Frage des Glaubens sondern des Wissens ist, ist auch diese Beziehung noch nicht bewiesen. Man kann aber zeigen, dass die Menge 
unter der oben genannten Annahme nicht leer ist. Dann nämlich ist das (nichtprobabilistische) Primzahlproblem weder ein - noch ein -vollständiges () Problem.
Folglich hat also die Komplexitätstheorie für eine Verschärfung der Frage nach der Existenz von Polynomzeitalgorithmen für Probleme gesorgt. Unter diesen Problemen versteht man jene, die nicht effizient gelöst werden können.
Trotz massivsten Anstrengungen vieler Wissenschaftler auf der ganzen Welt ist es nicht gelungen auch nur ein einziges -Problem in Polynomzeit zu lösen. Das lässt die Vermutung zu, dass es keine Polynomzeitlösungen für alle -Probleme gibt.
Die -Vollständigkeit sorgt nun für eine erneute Zuspitzung der immer noch stehenden Frage: 
. Es ist nur nötig für ein einziges -vollständiges Problem zu zeigen, dass ein Lösungsalgorithmus in existiert. Ist dieser Beweis erbracht so gilt dies für alle -Probleme. Folgender Satz bringt diese Tatsache auf den Punkt.
- Satz: Wenn ein -vollständiges Problem ist, dann gilt:
Der Beweis für das Verhältnis zwischen und wäre erbracht und eines der am häufigsten betrachteten Probleme der Informatik wäre gelöst.
Schlussendlich steht fest, dass die -vollständigen Probleme die schwierigsten überhaupt sind. Zum jetzigen Zeitpunkt existieren etwa 1000 relevanter Probleme, die alle durch polynomiale Reduktion hergeleitet wurden. Es ist nicht bekannt, ob alle -Probleme auch -vollständig sind oder nicht.
Stephen A. Cook
Zur Person Cook
Stephen A. Cook
Einer der bedeutesten Professoren der Informatik ist Stephen Arthur Cook. Er wurde am 14.Dezember 1939 in Buffalo, New York geboren und lebt heute in Kanada, wo er an der University of Toronto unterrichtet. Die größte Aufmerksamkeit widmete er der Komplexitätstheorie, in der er 1971 mit dem "Satz von Cook" berühmt wurde und 1982 den Turing Award erhielt, welcher an Personen verliehen wird, die besonders zur Entwicklung der Informatik beigetragen haben.
Satz von COOK
Für das Arbeiten mit dem "Satz von Cook" ist es wichtig zu wissen, was eigentlich das SAT-Problem ist. Das satisfiability problem, zu Deutsch das Erfüllbarkeitsproblem der Aussagenlogik, prüft, ob eine aussagenlogische Formel erfüllbar ist. Es ist also gefragt, wie die booleschen Belegungen der Variablen 
aussehen müssen, damit ein gegebener Ausdruck wahr wird. Damit dieses Problem deterministisch gelöst werden kann, muss eine Tabelle mit allen möglichen Belegungen der Variablen erstellt werden. Bei 
Variablen gibt es dabei 
mögliche Belegungen.
Als Spezialfall des SAT ist noch 3-SAT zu nennen. Hierbei besitzt der gegebene Ausdruck maximal drei Variablen pro Oder-Term. Ein Beispiel hierfür ist:
Da es eine deterministische Lösung gibt, könnte man annehmen, dass dieses Problem in liegt, was aber nicht sicher ist. Sicher ist nur, dass es in liegt. Weiterhin konnte festgestellt werden, dass dieses Problem -vollständig ist.
Um Probleme als -vollständig zu identifizieren, müssen sie auf ein ähnliches Problem polynomial reduziert werden. Das setzt aber voraus, dass es wenigstens ein Problem gibt, dessen -Vollständigkeit nicht durch Reduktion nachgewiesen wurde, da es sich ja auf kein anderes -vollständiges Problem nachweisen ließ. Dieses Problem existiert auch. Es wurde von Stephen A. Cook durch den "Satz von Cook" nachgewiesen, dass das Erfüllbarkeitsproblem der Aussagenlogik (kurz: SAT) -vollständig ist. Bewiesen wurde es mittels einer Turingmaschine, wobei jedes Merkmal der Maschine als aussagenlogische Formel interpretiert wird.
Das SAT-Problem ist somit das erste Problem, für das die -Vollständigkeit ohne polynomiale Reduktion nachgewiesen werden konnte. Jedes Problem lässt sich auf das Wahrheits-Belegungs-Problem von Cook umschreiben. Sollte eines dieser Probleme vom Typ sein, wären alle -Probleme letztendlich einfach, also in .
CLIQUEN-Problem
Bei dem sogenannten Cliquenproblem handelt es sich um ein NP-vollständiges Problem, welche durch die Reduktion auf 3SAT nachgewiesen wurde. Für beliebige ungerichtete Graphen ohne Mehrfachkanten soll festgestellt werden, ob 
einen vollständigen Teilgraphen 
, also eine Clique der Ordnung mit 
und 
besitzt. 
bezeichnet die Ecken und 
die Kanten eins Graphen. Paarweise verschiedene 
und 
sollen in 
durch Kanten miteinander verbunden sein. Anders ausgedrückt handelt es sich bei 
, der Teilmenge von um eine Clique, wenn zwei verschiedene aus stammende Knoten durch eine Kante miteinander verbunden sind. Wenn stets zwei beliebige Knoten aus nicht miteinander verbunden, so handelt es sich bei um eine stabile oder auch unabhängige Menge.
NP-Vollständigkeitsbeweis
Wir haben bereits die Eigenschaften von -schweren und darauf aufbauend von -vollständigen Problemen geklärt. Wie aber kann man nun nachweisen, dass ein Problem -vollständig ist? Noch dazu wenn dieses Problem vollkommen unbekannt und dem entsprechend neu ist! Die Antwort haben wir in der Tat schon bei den -schweren Problemen gegeben und diese lautet wie folgt: Polynomiale Reduktion (unter Ausnutzung der Transitivität von ) eines bereits bekannten -vollständigen Problems auf das "neue" Problem . Dazu sind vier Schritte erforderlich:
- 1. Zeige, dass
gilt.
- 2. Wähle ein -vollständiges Problem , das ähnelt.
- 3. Definiere eine polynomielle Transformation
, die Eingaben für in Eingaben für überführt.
- 4. Zeige, dass
gilt.
Als Beispiel soll das bekannte Problem TSP (Rundreiseproblem) dienen. Wir wollen beweisen, dass es sich bei TSP um ein -vollständiges Problem handelt. Wie bereits erwähnt brauchen wir ein bereits bekanntes -vollständiges Problem. Der HAMILTON-Kreis bietet sich dafür mehr als an. Ziel des HAMILTON-Kreises ist es jeden Punkt einmal zu besuchen, wobei kein Punkt doppelt genommen werden darf, ausgenommen ist der Startpunkt, der gleichzeitig den Endpunkt markiert. Das folgende Bild zeigt dies grafisch.
Wie auch beim Rundreiseproblem verlangt, entsteht ein geschlossener "Kreis". HAMILTON eignet sich also hervorragend. Alles Weitere wird analog zur bereits erklärten polynomialen Reduktion durchgeführt.
Dieses Beispiel mag sehr einfach anmuten, da sich die beiden Probleme unwahrscheinlich ähneln, jedoch ging bereits schon früher die Warnung raus, dass diese vermeintlich ähnlichen Formulierungen in keinster Weise einen Hinweis auf die Schwere des Problems geben. Auch hierfür soll ein Beispiel genannt werden. Der EULER-Kreis scheint mit dem HAMILTON-Kreis sehr verwandt. Viele Sachverhalte mögen sogar identisch sein. Um das Ganze zu Visualisieren wurde hier Schemecode mit dem Highligth Turtle benutzt.
Wie man sieht hat der EULER-Kreis gewisse Ähnlichkeiten mit dem bekannten Kinderspiel "Haus vom Nikolaus", jedoch ist zu beachten, dass es sich beim "Haus vom Nikolaus" um einen EULER-Weg handelt. Beim EULER-Kreis ist zu beachten, dass jede Kante nur einmal besucht werden darf, was eine gerade Anzahl von abgehenden und ankommenden Kanten voraus setzt. Das Haus vom Nikolaus alias EULER-Weg stellt diese Bedingung nicht. Die Idee des EULER-Weges ist es jede Kante nur einmal benutzen zu dürfen. Modifiziert man das Haus vom Nikolaus geringfügig erhält man einen EULER-Kreis. Es ist dabei zu unterstreichen, dass jede Kante einmal besucht werden muss.
Wir haben also einen EULER-Kreis, bei dem jede Kante genau einmal benutzt werden muss und wir haben den HAMILTON-Kreis, bei dem jeder Knoten einmal besucht werden muss. Augenscheinlich sehr ähnliche Probleme. Fest steht, dass die Anzahl der indizierten Kanten gerade sein muss und mit dieser Erkenntnis ist auch sicher, dass die Feststellung dieser Eigenschaft für jeden Knoten eines gegebenen Graphen in Polynomzeit erfolgen kann. Fazit ist, dass der EULER-Kreis in P liegt und, trotz der vermuteten Ähnlichkeit mit dem HAMILTON-Kreis, absolut keine Übereinstimmung mit dem Selben bezogen auf die Schwere zur Lösung vorhanden ist. Der EULER-Kreis ist ein leichtes und der HAMILTON-Kreis, ganz im Gegensatz dazu, ein schweres Problem.
Praktische Unlösbarkeit
Nun gibt es ja auch viele Probleme, die mit dem heutigen Stand der Technik nicht gelöst werden können, oder deren Berechnung aufwandsmäßig einfach unmöglich ist. Aber gerade wegen dieser Eigenschaft der Unlösbarkeit sind sie für einen bestimmten Bereich der Informatik interessant: Die Kryptographie. Hier werden Ver- und Entschlüsselungsverfahren gesucht, die nicht so leicht, oder am besten gar nicht zu knacken sind. Die Schwierigkeit dabei liegt im Schlüssel: Jedes Verschlüsselungsverfahren benötigt irgendeine Art an Schlüssel, sei es die Anzahl der Verschiebungen der Buchstaben des Alphabets oder das Codewort zum Entschlüsseln scheinbar sinnloser Zeichen. Problem ist jetzt, den Schlüssel sicher an den Empfänger zu übertragen, ohne das Dritte ihn ebenfalls einsehen können. Um den entgegenwirken zu können, werden öffentliche Schlüssel verwendet, wie beim RSA-Verfahren, wobei RSA von den Anfangsbuchstaben der Entwickler Rivest, Shamir und Adleman abgeleitet sind. Der öffentliche Schlüssel ist jedem verfügbar, der eine Nachricht an einen Empfänger übertragen möchte.
Im Falle des RSA-Verfahrens besteht dieser Schlüssel aus zwei Teilen 
und 
. Der Empfänger kann die Nachricht mit Hilfe seines persönlichen Schlüssels 
entschlüsseln. Dieser Schlüssel besteht aus dem Teil 
, der geheim gehalten werden sollte. Bei dieser Entschlüsselung wird auch der Teil aus dem öffentlichen Schlüssel verwendet. Um die Nachricht entschlüsseln zu können, ohne im Besitz eines privaten Schlüssels zu sein, müssen die beiden Schlüsselteile und bekannt sein, da sich aus ihnen ermitteln lässt. Um wiederum kennen zu können, müssen die beiden Primzahlen 
und 
berechnet werden, da sich aus der Multiplikation der beiden ergibt 
. Allerdings sind es sehr große Primzahlen, die nur mit exponentiellem Aufwand bestimmbar sind. Selbst beim Raten bräuchte ein Codeknacker so viel Glück wie jemand, der 30mal hintereinander sechs Richtige im Lotto hat. Als Ansatz bleibt also nur die Faktorisierung von . Es ist also auch nicht überraschend, dass bisher noch kein effizienter Algorithmus zum Knacken des RSA-Verfahrens entdeckt worden ist.
Frank P. Ramsey
Zur Person Ramsey
Frank P. Ramsey
Eine weitere wichtige Persönlichkeit für die Informatik, speziell die Komplexitätstheorie, ist Frank Plumpton Ramsey, ein britischer Mathematiker und Logiker. Er wurde am 22. Februar 1903 in Cambridge als Sohn eines Mathematikers geboren und starb am 19. Januar 1930 an Hepatitis, mit der er sich bei einer Unterleibsoperation infizierte. Bevor er selbst Mathematik am Trinity College in Cambridge studierte, besuchte Ramsey das College in Winchester. Ramsey war in Cambridge recht schnell in aller Munde und beeindruckte viele Akademiker durch seine überragende Intelligenz. Politisch gesehen war er linksorientiert und seine Ehefrau bezeichnete ihn als einen „militanten Atheisten“.
Neben seinen Beiträgen zur Mathematik brachte er sich auch in der Komplexitätstheorie mit dem "Ramsey-Problem" ein.
RAMSEY-Problem
Da das RAMSEY-Problem durch den gleichnamigen Mathematiker und Logiker formuliert wurde, erhielt es auch selbigen Namen. Allerdings ist es auch unter der Bezeichnung Party-Problem zu finden. Dieses Problem scheint rein von der Formulierung her nicht sonderlich schwer zu sein, ist aber in Wirklichkeit eines der härtesten Probleme in der Komplexitätstheorie. Es lautet folgendermaßen:
- "Wie viele Gäste muss man einladen, damit es auf jeden Fall (mindestens)
Personen gibt, die sich gegenseitig kennen, oder (mindestens) Personen, die sich gegenseitig nicht kennen?"
Hierbei ist zu beachten, dass der Partygeber selbst nicht weiß, ob sich die Gäste kennen, oder nicht. Um das Problem besser zu verstehen, kann man es mit der Aussage von D.J. Kleitman vergleichen, in der es sinngemäß heißt, dass wenn man drei Gäste einlädt, mindestens zwei dasselbe Geschlecht haben.
Will man das RAMSEY-Problem graphisch darstellen, wird man eine gewisse Ähnlichkeit mit dem Cliquenproblem erkennen, da es sich quasi um zwei Probleme dieser Art handelt: Die beiden Graphen, die zur Darstellung benötigt werden, färbt man unterschiedlich ein, z.B. blau für "kennen" und rot für "nicht kennen". Eine Kante zwischen zwei Ecken ist entweder rot oder blau eingefärbt. Trägt man jetzt beispielsweise alle roten Kanten ein, sind die noch offenen Kanten alle blauen. Weiterhin werden die Knoten zur besseren Übersicht durchnummeriert.
Eine weitere Vorgehensweise ist folgende: Man zeichnet alle möglichen Verbindungen in einen Graphen ein und sucht die Cliquen raus, welche die Anforderungen erfüllen.
Ein Lösungsbeispiel ist die Ramsey-Zahl mit 
und 
, bei der 3 Gäste eingeladen werden müssen, damit die Anforderungen erfüllt sind, also: 
. Es gibt mehrere Möglichkeiten für die graphische Lösung:
- Alle Kanten werden rot gefärbt
- Alle Kanten werden blau gefärbt
- Zwei Kanten werden blau gefärbt und eine rot
- Zwei Kanten werden rot gefärbt und eine blau
Für erstens und zweitens bedeutete das, dass sich entweder alle kennen oder sich alle nicht kennen und für drittens und viertens heißt das, dass sich entweder zwei Personen kennen und die dritte niemand kennt, oder dass sich zwei Personen kennen, aber die dritte jemanden kennt. Anders gesagt gilt also entweder m oder n oder beide. Vergleich bar ist dies mit einem aussagenlogischen Oder, welches nur nicht wahr wird, wenn keine der Variablen wahr ist.
Bis heute konnten bisher nur wenige Ramsey-Zahlen berechnet werden, da sich durch die Bedingungen sehr große Zahlen ergeben, die nur exponentiell ermittelt werden können. Daher sind bisher auch nur für sehr kleine m und n die Ramsey-Zahlen bekannt.
Pseudopolynomiale Algorithmen
Bei einigen Problemlösungen könnte man beinahe annehmen, dass das --Problem gelöst worden ist, da durch verschiedene Techniken eine scheinbar deterministische Lösung zu einem eigentlich nichtdeterministisch lösbaren Problem gefunden worden ist und umgekehrt, wie es scheinbar beim 0/1-Rucksackproblem der Fall ist, welches mittels dynamischer Programmierung deterministisch lösbar ist.
Allerdings sind solche Algorithmen pseudopolynomial. Dabei handelt es sich um spezielle Algorithmen, deren Laufzeit polynomial ist, wenn die Größe aller in der Eingabe vorkommenden Zahlen polynomial in der Eingabelänge beschränkt ist. Solche Algorithmen gibt es nur sehr selten. Existiert jedoch zu einem Problem ein pseudopolynomialer Algorithmus, so ist dieses Problem stark -vollständig, ansonsten handelt es sich um ein -schwaches Problem.
Übungsaufgaben
1) Für welche Belegung der Variablen werden die folgenden Formeln wahr? (Tabellenform!)
- a)
- b)
2) Stellen Sie die oben gegebenen Formeln in graphischer Form dar. Wie schätzen Sie die Übersichtlichkeit, vor allem der Formel aus b.) ein?
3) Markieren Sie alle vorhandenen CLIQUEN nach dem Prinzip der Optimierung (größtmögliche CLIQUEN). Kennzeichnen Sie die größte CLIQUE!
4) Reduzieren Sie CLIQUE auf die folgende aussagenlogische Formel (3-SAT). Nutzen Sie die Wahrheitstabelle um Ihr Ergebnis zu überprüfen.
5) Welche Aussage verbirgt sich hinter dem Satz von COOK?
6) Stellen Sie vier mögliche Lösungen für die Ramsey-Zahl R(3,3) = 6 graphisch dar.
Quellen
Literatur
- [1] Christian Wagenknecht
- Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003 - ISBN 3-446-22314-2
- [2] Robert Sedgewick
- Algorithmen, 3. unveränderte Auflage - Addison-Wesley, 1994 - ISBN 3-89319-402-9
- [3] Volker Turau
- Algorithmische Graphentheorie, Addison-Wesley, 1996 - ISBN 3-89319-938-1
- [4] Uwe Schöning
- Theoretische Informatik kurz gefasst, Wissenschaftsverlag Mannheim Leipzig Wien Zürich, 1993 - ISBN 3-411-15641-4
Weblinks
- [1] Wikipedia - P-NP-Problem
- [2] Wikipedia - Komplexitätsklassen
- [3] Wikipedia - Komplexitätstheorie
- [4] Wikipedia - Liste der Komplexitätsklassen
- [5] Wikipedia - Stephen A. Cook
- [6] Wikipedia - Frank P. Ramsey
- [7] Wikipedia - Millennium-Probleme
- [8] Uni-Protokolle - P-NP-Problem
- [9] Universität Bremen - P-NP-Problem
Siehe auch
- [1] Hompage von Stephen A. Cook
- http://www.cs.toronto.edu/~sacook/
- [2] Clay Mathematics Institute
- http://www.claymath.org/millennium/
- [3] MacTutor History of Mathematics archive
- http://www-history.mcs.st-andrews.ac.uk/Biographies/Ramsey.html
