In den Arbeiten „The convenience of tilings“ und „Domino-Tiling Games“ werden sogenannte Domino-Spiele betrachtet. Domino-Spiele sind für die Komplexitätstheorie interessant, da sie dank ihrer Einfachheit und Anschaulichkeit Ansätze für diverse Reduktionen liefern. Auch lassen sich die verschiedenen Domino-Spiel-Typen gerade deshalb leicht unterschiedlichen Komplexitätsklassen zuordnen. Diese Arbeit soll die Ergebnisse der beiden genannten Veröffentlichungen erläutern und für eine eigene Anwendung aufgreifen.
Dazu folgt zunächst eine Einführung in die Komplexitätstheorie, welche die Grundbegriffe erläutert, die für den weiteren Verlauf der Arbeit notwendig sind. Im zweiten Teil der Arbeit werden Domino-Spiele sowie ihre Zwei-Spieler-Varianten und ihr Zusammenhang mit Turingmaschinen, und damit auch mit der Komplexitätstheorie, beschrieben. Zuletzt wird das zuvor gewonnene Wissen auf eine erfundene Zwei-Spieler-Version des Problems EXACT COVER angewendet, so dass seine Komplexität bestimmt werden kann.
Inhaltsverzeichnis
1 Einleitung
2 Komplexitätstheorie
2.1 Turingmaschinen
2.2 Komplexitätsklassen
2.2.1 TIME, P und EXPTIME
2.2.2 NTIME und NP
2.3 Reduktionen
2.4 NP-Härte und NP-Vollständigkeit
2.5 SPACE und PSPACE
3 Domino-Spiele in der Komplexitätstheorie
3.1 Einführung
3.2 Domino-Spiele
3.2.1 Spielregeln
3.2.2 BOUNDED TILING
3.3 Vom Berechnungsmodell hin zu den Domino-Spielen
3.3.1 Zustandsdiagramme
3.3.2 Reduktion von Turingmaschinen auf BOUNDED TILING
3.4 Zwei-Spieler Domino-Spiele
3.4.1 Allgemeines über Zwei-Spieler Domino-Spiele
3.4.2 ZWEI-SPIELER BOUNDED TILING
3.4.3 ZWEI-SPIELER EXACT COVER
3.4.4 Reduktion von ZWEI-SPIELER BOUNDED TILING auf ZWEI-SPIELER EXACT COVER
4 Schluss
Zielsetzung und thematische Schwerpunkte
Das Hauptziel dieser Arbeit ist es, die Ergebnisse bestehender Veröffentlichungen zu Domino-Spielen zu erläutern und diese auf eine eigene Zwei-Spieler-Version des Problems EXACT COVER anzuwenden, um deren Komplexität zu bestimmen.
- Grundlagen der Komplexitätstheorie (Turingmaschinen, Komplexitätsklassen, Reduktionen)
- Einführung und Analyse von Domino-Spielen als mathematische Rechnermodelle
- Untersuchung der Komplexität von BOUNDED TILING und dessen Zwei-Spieler-Varianten
- Durchführung einer Reduktion von ZWEI-SPIELER BOUNDED TILING auf ZWEI-SPIELER EXACT COVER
Auszug aus dem Buch
3.3.1 Zustandsdiagramme
Um eine Turingmaschine mit Hilfe von Domino-Spielen darstellen zu können, müssen zunächst sogenannte Zustandsdiagramme für Turingmaschinen eingeführt werden.
In Abschnitt 2.1 wurde eine Konfiguration einer Turingmaschine mit α1(q, a) α2 angegeben. Schreibt man alle Konfigurationen vom Beginn einer Berechnung an untereinander auf, so erhält man ein sogenanntes Zustandsdiagramm, das die gesamte Berechnung der Maschine veranschaulicht. Als Beispiel dient eine Turingmaschine M = (Q, Σ, Γ, δ, q0, ✄,, F) mit der Übergangsrelation δ = {(q0, 0, q0, 0, R),(q1, 0, q1, 0, R),(q0, 1, q1, 1, R),(q1, 1, q0, 1, R),(q0,, q2, 0, 0),(q1, , q2, 1, 0)}. Das Programm zählt von links nach rechts die Anzahl der Einsen in der Eingabe und ersetzt das erste Blank-Symbol durch 0 für eine gerade oder durch 1 für eine ungerade Anzahl. Die Menge aller Zustände ist Q = {q0, q1, q2}, der Startzustand ist q0 und die Menge von Endzuständen ist F = {q2}. Das Bandalphabet ist Γ = {0, 1, ✄,} und Eingabesymbole sind Σ = {0, 1}.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Thematik der Domino-Spiele ein und skizziert den Aufbau der Arbeit sowie die Anwendung auf das Problem EXACT COVER.
2 Komplexitätstheorie: Dieses Kapitel erläutert die theoretischen Grundlagen wie Turingmaschinen, Komplexitätsklassen und Reduktionen, die für das Verständnis der Arbeit notwendig sind.
3 Domino-Spiele in der Komplexitätstheorie: Das Hauptkapitel behandelt Domino-Spiele als mathematische Modellierung für Berechnungen, analysiert deren Komplexität und führt die Reduktion auf Zwei-Spieler-Varianten durch.
4 Schluss: Das Schlusswort fasst zusammen, dass Domino-Spiele eine anschauliche und effektive Methode für Reduktionen innerhalb der Komplexitätstheorie darstellen.
Schlüsselwörter
Domino-Spiele, Komplexitätstheorie, Turingmaschine, Komplexitätsklassen, BOUNDED TILING, ZWEI-SPIELER BOUNDED TILING, ZWEI-SPIELER EXACT COVER, Reduktion, NP-Vollständigkeit, PSPACE-Vollständigkeit, Spieltheorie, Kacheltypen, Zustandsdiagramme, Berechnungsmodelle, EXAKTE ÜBERDECKUNG
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit untersucht Domino-Spiele im Kontext der Komplexitätstheorie und zeigt, wie man Berechnungen von Turingmaschinen durch diese Spiele kodieren kann.
Was sind die zentralen Themenfelder der Arbeit?
Die Arbeit fokussiert auf Komplexitätstheorie, formale Berechnungsmodelle (Turingmaschinen) sowie Domino-Tiling-Probleme und deren Zwei-Spieler-Varianten.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die Erläuterung der Ergebnisse bekannter Domino-Tiling-Veröffentlichungen und die Bestimmung der Komplexität einer eigenen Zwei-Spieler-Version des Problems EXACT COVER.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden formale Methoden der theoretischen Informatik verwendet, insbesondere die Reduktion von Problemen zur Beweisführung von NP- und PSPACE-Vollständigkeit.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil widmet sich der Definition und Modellierung von Domino-Spielen, der Reduktion von Turingmaschinen auf BOUNDED TILING sowie der Analyse von Zwei-Spieler-Varianten dieser Probleme.
Welche Schlüsselwörter charakterisieren die Arbeit am besten?
Zentral sind Begriffe wie Domino-Spiele, Komplexitätsklassen, Reduktion, NP-Vollständigkeit und PSPACE-Vollständigkeit.
Was ist der wesentliche Unterschied zwischen einer Turingmaschine und einem Domino-Spiel in dieser Arbeit?
Die Turingmaschine ist ein abstraktes Berechnungsmodell, während das Domino-Spiel als visuelle und anschauliche Repräsentation dient, um die Berechnungen der Maschine zu kodieren.
Warum ist das Ergebnis für ZWEI-SPIELER EXACT COVER besonders relevant?
Das Ergebnis zeigt, dass diese spezifische Zwei-Spieler-Version PSPACE-vollständig ist, was durch eine direkte Reduktion von ZWEI-SPIELER BOUNDED TILING bewiesen wird.
- Quote paper
- Uli Holtmann (Author), 2013, Tiling-Games. Eine Anwendung von Dominospielen und ihre Komplexität, Munich, GRIN Verlag, https://www.grin.com/document/266205
