KomplexitÃ¤tstheorie

Glossar
· Hauptseite · Zufälliger Artikel · Portal liste
Diskussion
· Diskussion : KomplexitÃ¤tstheorie
Webkatalog
· Übersicht · Eigene Artikel · Seite vorschlagen
Aktuelles
· Seite der Woche · Newsletter · Today in History · Kreuzworträtsel
Weitere Inhalte
· Einkaufsmeile · Begriffslexikon · Multimedia
Suche
· Geschi.de · nach Jahren · Weltchronik.de · Geschichtsreferate
Interna
· Seitenneuigkeiten · Hilfe zur Seite · Impressum

Jahres-Sprung
Jahreszahl eingeben: >Chronik2000-Homepage<

Stichpunkte

Allgemein
	Die KomplexitÃ¤tstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der KomplexitÃ¤t von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen
	sowie der GÃ¼te der sie lÃ¶senden Algorithmen
	meist auf die Rechenzeit oder den Speicherplatzbedarf
	Die Untersuchung der KomplexitÃ¤t bezieht sich dabei auf den Ressourcenverbrauch der Algorithmen
	worst und average case fÃ¼r ProblemgrÃ¶ÃŸen 1.7 Untere und obere Schranken fÃ¼r Probleme 2 Maschinenmodelle in der KomplexitÃ¤tstheorie 2.1 Kostenfunktionen 2.2 KostenmaÃŸe 2.3 Maschinenmodelle und Probleme 2.4 HÃ¤ufig eingesetzte Maschinenmodelle 2.5 Modellmodifikationen fÃ¼r Speicherplatzanalysen 3 Verwendung und Rechtfertigung der O-Notation 4 Bildung von KomplexitÃ¤tsklassen 4.1 EinflussgrÃ¶ÃŸen bei der Bildung von KomplexitÃ¤tsklassen 4.2 Anforderungen an Schrankenfunktionen 4.3 HierarchiesÃ¤tze 4.3.1 Zeithierarchiesatz 4.3.2 Raumhierarchiesatz 4.3.3 WofÃ¼r die HierarchiesÃ¤tze nicht gelten 4.4 Wichtige Zeitklassen 4.5 Wichtige Raumklassen 4.6 Komplementbildungen 5 Sprachen und KomplexitÃ¤tsklassen 6 Anwendungsbereiche [Bearbeiten]
	die sich mit der Frage beschÃ¤ftigt
	"Verbergen") 1 Probleme aus Sicht der KomplexitÃ¤tstheorie 1.1 Probleme als formale Sprachen 1.2 Probleminstanzen 1.3 ProblemreprÃ¤sentationen 1.4 Entscheidungsprobleme 1.5 ProblemgrÃ¶ÃŸen 1.6 Best
	welche Probleme prinzipell algorithmisch gelÃ¶st werden kÃ¶nnen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Die KomplexitÃ¤tstheorie unterscheidet sich von der Berechenbarkeitstheorie
Probleme aus Sicht der KomplexitÃ¤tstheorie
	[Bearbeiten]
Probleme als formale Sprachen
	Den zentralen Gegenstand der KomplexitÃ¤tstheorie bilden Probleme
	ob es zu der Sprache gehÃ¶rt oder nicht
	Ein Problem wird dabei als formale Sprache verstanden
	und die Berechnung besteht darin
	fÃ¼r ein gegebenes Wort zu entscheiden
	Diese Vorgehensweise erklÃ¤rt sich anhand folgender Ãœberlegung: Jede Maschine ist zu nichts anderem in der Lage als zur Manipulation von Symbolen
	Symbolfolgen werden als Worte
	Wortmengen werden als Sprachen betrachtet
	Probleminstanzen mÃ¼ssen der Maschine also in Form konkreter Worte zur Berechnung Ã¼bergeben werden
	dass die Maschine fÃ¼r ein gegebenes Wort nur meldet
	Wie im untenstehenden Abschnitt Ã¼ber Entscheidungsprobleme noch ausgefÃ¼hrt wird
	einigt man sich in der Regel darauf
	ob das damit beschriebene Problem lÃ¶sbar ist oder nicht
	um das Akzeptieren der AuÃŸenwelt mitzuteilen).Ãœbertragen in die Problemwelt bedeutet dies also
	dass das Problem eine LÃ¶sung hat
	Man sagt dann: Die Maschine akzeptiert das Wort (sie gibt z.B. eine 1 aus
	Aus der Sicht der Maschine stellen sich Probleme demnach als Sprachen dar
	welche die Maschine akzeptiert. [Bearbeiten]
	Die fÃ¼r eine Maschine lÃ¶sbaren Probleme werden gerade durch die Worte reprÃ¤sentiert
Probleminstanzen
	dass der Maschine Probleminstanzen in Form konkreter Worte Ã¼bergeben werden
	Im vorhergehenden Abschnitt war bereits davon die Rede
	Eine Probleminstanz ist nicht mit dem Problem selbst zu verwechseln
	Ein Problem stellt in der KomplexitÃ¤tstheorie eine abstrakte Fragestellung dar: Man mÃ¶chte zu Aussagen fÃ¼r beliebige Instanzen von Problemen gelangen
	Eine Instanz des Traveling-Salesman-Problems kÃ¶nnte z.B. das Finden einer mÃ¶glichst optimalen Route durch die LandeshauptstÃ¤dte Deutschlands sein
	Eine Aussage Ã¼ber diese Route hat jedoch nur begrenzten Wert fÃ¼r andere Problemstellungen
	die mit der Optimierung einer Route zu tun haben
	In der KomplexitÃ¤tstheorie interessiert man sich daher fÃ¼r Aussagen
	die unabhÃ¤ngig von konkreten Instanzen sind. [Bearbeiten]
ProblemreprÃ¤sentationen
	Das oben Ã¼ber Probleminstanzen Gesagte trifft auch auf die ReprÃ¤sentation von Problemen zu
	Auch wenn letztlich fÃ¼r BeweisfÃ¼hrungen eine konkrete ReprÃ¤sentation definiert werden muss
	so versucht man die Betrachtung unabhÃ¤ngig von ReprÃ¤sentationen zu halten
	Dies kann etwa erreicht werden
	dass die gewÃ¤hlte ReprÃ¤sentation bei Bedarf ohne allzu groÃŸen Aufwand in eine andere ReprÃ¤sentation transformiert werden kann
	ohne dass sich hierdurch die BerechnungsaufwÃ¤nde insgesamt signifikant verÃ¤ndern
	indem man sicherstellt
	ist u.a. die Auswahl eines geeigneten universellen Maschinenmodells von Bedeutung. [Bearbeiten]
	Um dies zu ermÃ¶glichen
Entscheidungsprobleme
	ProblemlÃ¶sungen zu generieren
	sondern begnÃ¼gt sich mit der Antwort
	ob ein Problem mit einem definierten Ressourcenaufwand lÃ¶sbar ist oder nicht
	Bild nicht gefundenleft DarÃ¼ber hinaus verzichtet man in der KomplexitÃ¤tstheorie oft darauf
	So formulierte Probleme bezeichnet man auch als Entscheidungsprobleme
	dass man sich im Rahmen der KomplexitÃ¤tsanalyse eine Behandlung der Ausgabe einer ProblemlÃ¶sung ersparen mÃ¶chte - zumal diese ohnehin meist von einer konkreten ReprÃ¤sentation abhÃ¤ngig ist. [Bearbeiten]
	Die Motivation dieser Vereinfachung besteht darin
ProblemgrÃ¶ÃŸen
	wie sich ein Algorithmus bei der Berechnung dieses Problems verhÃ¤lt
	so mÃ¶chte man nun Aussagen darÃ¼ber treffen
	Hat man ein Problem mathematisch-formal definiert (z.B. das Traveling-Salesman-Problem in Form eines Graphen)
	Potentiell wÃ¤ren viele verschiedene Aspekte des Problems zu betrachten
	Normalerweise existiert jedoch eine GrÃ¶ÃŸe
	die das Verhalten des Algorithmus im Hinblick auf den Ressourcenverbrauch maÃŸgeblich beeinflusst
	Diese GrÃ¶ÃŸe bezeichnet man als ProblemgrÃ¶ÃŸe oder EingabelÃ¤nge
	Man untersucht nun das Verhalten des Algorithmus im Hinblick auf unterschiedliche ProblemgrÃ¶ÃŸen
	da es hier Ã¼berhaupt nur eine mÃ¶gliche LÃ¶sung gibt und diese folglich auch optimal sein muss
	So ist beispielsweise das Traveling-Salesman-Problem fÃ¼r die EingabelÃ¤nge 2 trivial
	dass der Algorithmus fÃ¼r grÃ¶ÃŸere Eingaben mehr Arbeit leisten muss
	Es ist jedoch zu erwarten
	exponentiell oder gar Ã¼berexponentiell? [Bearbeiten]
	polynomiell
	Die KomplexitÃ¤tstheorie interessiert sich nun fÃ¼r die Frage: Wieviel Mehrarbeit ist fÃ¼r wachsende ProblemgrÃ¶ÃŸen notwendig? Steigt der Aufwand zum Beispiel linear
Best, worst und average case fÃ¼r ProblemgrÃ¶ÃŸen
	Auch innerhalb einer ProblemgrÃ¶ÃŸe lassen sich verschiedene Verhaltensweisen von Algorithmen beobachten
	So hat das Traveling-Salesman-Problem fÃ¼r die 16 deutschen LandeshauptstÃ¤dte dieselbe ProblemgrÃ¶ÃŸe n=16 wie das Finden einer Route durch 16 europÃ¤ische HauptstÃ¤dte
	dass ein Algorithmus unter den unterschiedlichen Bedingungen (selbst bei gleicher ProblemgrÃ¶ÃŸe) jeweils gleich gut arbeitet
	Es ist keineswegs zu erwarten
	gruppiert man diese zumeist grob in drei Gruppen: best case
	worst case und average case
	Da es jedoch praktisch unendlich viele Instanzen fÃ¼r ein Problem geben kann
	Diese stehen fÃ¼r die Fragen: Best case: Wie arbeitet der Algorithmus (in Bezug auf die in Frage stehende Ressource) im besten Fall? Worst case: Wie arbeitet der Algorithmus im schlimmsten Fall? Average case: Wie arbeitet der Algorithmus durchschnittlich (wobei die zugrundegelegte Verteilung fÃ¼r die Berechnung eines Durchschnitts nicht immer offensichtlich ist)? [Bearbeiten]
Untere und obere Schranken fÃ¼r Probleme
	aber feste EingabelÃ¤ngen
	Die Betrachtung von best
	worst und average case bezieht sich auf zwar beliebige
	ist diese Sichtweise fÃ¼r die KomplexitÃ¤tstheorie meist nicht abstrakt genug
	Auch wenn die Betrachtung konkreter EingabelÃ¤ngen in der Praxis von groÃŸem Interesse sein kann
	kann sich aufgrund technischer Entwicklungen sehr schnell Ã¤ndern
	Welche EingabelÃ¤nge als groÃŸ oder praktisch relevant gilt
	Es ist daher gerechtfertigt
	das Verhalten von Algorithmen in Bezug auf ein Problem gÃ¤nzlich unabhÃ¤ngig von konkreten EingabelÃ¤ngen zu untersuchen
	Man betrachtet hierzu das Verhalten der Algorithmen fÃ¼r immer grÃ¶ÃŸer werdende
	potentiell unendlich groÃŸe EingabelÃ¤ngen und spricht auch vom asymptotischen Verhalten des jeweiligen Algorithmus
	Bei dieser Untersuchung des asymptotischen Ressourcenverbrauchs spielen untere und obere Schranken eine zentrale Rolle
	welche Ressourcen fÃ¼r die Entscheidung eines Problems mindestens und hÃ¶chstens benÃ¶tigt werden
	Man mÃ¶chte also wissen
	dass ein bestimmter Problemtyp mindestens einen bestimmten Ressourcenverbrauch beansprucht und es folglich keinen Algorithmus geben kann
	der das Problem mit geringeren Ressourcen entscheiden kann
	FÃ¼r die KomplexitÃ¤tstheorie sind vor allem die unteren Schranken von Interesse: Man mÃ¶chte zeigen
	der in der Regel durch die Analyse konkreter Algorithmen erfolgen kann
	muss sich also eine Untersuchung der unteren Schranken auch auf Algorithmen beziehen
	die ein bestimmtes Problem entscheiden
	Im Gegensatz zum Nachweis von oberen Schranken
	auch der noch unbekannten Algorithmen
	also auf die Menge aller
	die noch garnicht gefunden wurden
	Dies erfordert eine grundlegend andere
	abstraktere Herangehensweise als die Analyse von bereits bekannten Algorithmen und gilt daher als schwer zugÃ¤nglicher Teilbereich der Informatik. [Bearbeiten]
Maschinenmodelle in der KomplexitÃ¤tstheorie
	[Bearbeiten]
Kostenfunktionen
	welche eine Zuordnung der Arbeitsschritte des Algorithmus zu den verbrauchten Ressourcen ermÃ¶glichen
	Zur Analyse des Ressourcenverbrauchs von Algorithmen sind geeignete Kostenfunktionen zu definieren
	welche Art von Arbeitsschritt einem Algorithmus Ã¼berhaupt erlaubt ist
	Um dies tun zu kÃ¶nnen
	muss zunÃ¤chst festgelegt werden
	Diese Festlegung erfolgt in der KomplexitÃ¤tstheorie Ã¼ber abstrakte Maschinenmodelle - wÃ¼rde man auf reale Rechnermodelle zurÃ¼ckgreifen
	so wÃ¤ren die gewonnenen Erkenntnisse bereits in wenigen Jahren Ã¼berholt
	Der Arbeitsschritt eines Algorithmus erfolgt in Form einer BefehlsausfÃ¼hrung auf einer bestimmten Maschine
	die eine Maschine ausfÃ¼hren kann
	Die Befehle
	sind dabei durch das jeweilige Modell streng limitiert
	DarÃ¼ber hinaus unterscheiden sich verschiedene Modelle etwa in der Handhabung des Speichers und in ihren FÃ¤higkeiten zur parallelen Verarbeitung
	d.h. der gleichzeitigen AusfÃ¼hrung mehrerer Befehle
	Die Definition der Kostenfunktion erfolgt nun durch eine Zuordnung von Kostenwerten zu den jeweils erlaubten Befehlen. [Bearbeiten]
KostenmaÃŸe
	HÃ¤ufig wird von unterschiedlichen Kosten fÃ¼r unterschiedliche Befehle abstrahiert und als Kostenwert fÃ¼r eine BefehlsausfÃ¼hrung immer 1 gesetzt
	Sind auf einer Maschine beispielsweise Addition und Multiplikation die erlaubten Operationen
	die im Laufe des Algorithmus berechnet werden mÃ¼ssen
	so zÃ¤hlt man fÃ¼r jede Addition und jede Multiplikation
	den Kostenwert von 1 hinzu
	Man spricht dann auch von einem uniformen KostenmaÃŸ
	auf dem die Operationen arbeiten
	wenn sich die erlaubten Operationen nicht gravierend unterscheiden und wenn der Wertebereich
	Ein solches Vorgehen ist dann gerechtfertigt
	nur eingeschrÃ¤nkt groÃŸ ist
	Dies wird schon fÃ¼r eine einfache Operation wie die Multiplikation klar: Das Produkt zweier einstelliger Dezimalziffern dÃ¼rfte sich ungleich schneller errechnen lassen als das Produkt zweier hundertstelliger Dezimalziffern
	Bei einem uniformen KostenmaÃŸ wÃ¼rde beide Operationen dennoch mit einem Kostenwert von 1 veranschlagt
	Sollten sich die mÃ¶glichen Operanden im Laufe eines Algorithmus tatsÃ¤chlich in so gravierend unterscheiden
	so muss ein realistischeres KostenmaÃŸ gewÃ¤hlt werden
	HÃ¤ufig wÃ¤hlt man dann das logarithmische KostenmaÃŸ
	Der Bezug auf den Logarithmus ergibt sich daraus
	dass sich eine n-stellige Dezimalzahl durch log n BinÃ¤rziffern darstellen lÃ¤sst
	Man wÃ¤hlt zur ReprÃ¤sentation der Operanden BinÃ¤rziffern aus und definiert die erlaubten boolschen Operationen
	so werden auch diese binÃ¤r codiert
	Sollte das jeweilige Maschinenmodell Adressen verwenden
	Auf diese Weise werden die Kosten Ã¼ber die LÃ¤nge der BinÃ¤rdarstellung logarithmisch gewichtet
	werden jedoch nur selten eingesetzt. [Bearbeiten]
	Andere KostenmaÃŸe sind mÃ¶glich
Maschinenmodelle und Probleme
	Man unterscheidet zwei Typen von Maschinenmodellen: deterministische Maschinen und nichtdeterministische Maschinen
	Von den meisten Maschinenmodellen existiert sowohl eine deterministische als auch eine nichtdeterministische Version
	lassen sich jedoch im allgemeinen erheblich leichter zu einem gegebenen Problem konstruieren
	Nichtdeterministische Maschinen verfÃ¼gen zwar Ã¼ber unrealistische FÃ¤higkeiten (sie "erraten" einen richtigen Pfad in einem Berechnungsbaum)
	konstruiert man daher zunÃ¤chst eine nichtdeterministische Maschinenversion und transformiert diese spÃ¤ter in eine deterministische
	Da eine Transformation von nichtdeterministischen in deterministische Maschinen immer relativ einfach mÃ¶glich ist
	Daraus geht eine wichtige Beweistechnik der KomplexitÃ¤tstheorie hervor: LÃ¤sst sich zu einem gegebenen Problem ein bestimmter Maschinentyp konstruieren
	auf dem das Problem mit bestimmten Kosten entschieden werden kann
	so kann damit bereits die KomplexitÃ¤t des Problems eingeschÃ¤tzt werden
	TatsÃ¤chlich werden sogar die unterschiedlichen Maschinenmodelle bei der Definition von KomplexitÃ¤tsklassen zugrundegelegt
	Dies entspricht einer Abstraktion von einem konkreten Algorithmus: Wenn ein Problem auf Maschine M entscheidbar ist (wobei ein entsprechender Algorithmus evtl. noch garnicht bekannt ist)
	so lÃ¤sst es sich unmittelbar einer bestimmten KomplexitÃ¤tsklasse zuordnen
	die von M definiert wird
	nÃ¤mlich derjenigen
	Dieses VerhÃ¤ltnis zwischen Problemen und Maschinenmodellen ermÃ¶glicht BeweisfÃ¼hrungen ohne die umstÃ¤ndliche Analyse von Algorithmen. [Bearbeiten]
HÃ¤ufig eingesetzte Maschinenmodelle
	insbesondere die parallele Registermaschine. [Bearbeiten]
	Besonders hÃ¤ufig eingesetzte Modelle sind: <gallery> Bild:Turingmaschine.png\|Turingmaschine Bild:Registermaschine-beispiel.png\|Registermaschine Bild:Kellerautomat.png\|Kellerautomat Bild:Nea02.png\|Endlicher Automat </gallery> Zur Untersuchung parallelisierbarer Probleme kÃ¶nnen darÃ¼ber hinaus auch parallelisierte Versionen dieser Maschinen zum Einsatz kommen
Modellmodifikationen fÃ¼r Speicherplatzanalysen
	Zur Untersuchung des Mindestspeicherbedarfs
	der fÃ¼r die LÃ¶sung von Problemen benÃ¶tigt wird
	nimmt man hÃ¤ufig die folgenden Modifikationen des verwendeten Maschinenmodells (in der Regel eine Turingmaschine) vor: Der Eingabespeicher darf nur gelesen werden. Auf die Ausgabe darf nur geschrieben werden
	Der Schreibkopf wird nur nach SchreibvorgÃ¤ngen und immer in dieselbe Richtung bewegt (falls das Maschinenmodell eine solche Bewegung vorsieht). FÃ¼r die Untersuchung des Speicherbedarfs dÃ¼rfen dann Ein- und Ausgabe der Maschine unberÃ¼cksichtigt bleiben
	Die Motivation fÃ¼r diese Ã„nderungen ist die folgende: WÃ¼rde z.B. der Eingabespeicher in die Speicherplatzanalyse einbezogen
	denn das Eingabewort hat ja immer genau die LÃ¤nge und damit den Speicherbedarf n
	so kÃ¶nnte kein Problem in weniger als O(n) Platzbedarf gelÃ¶st werden
	verhindert man
	dass sie fÃ¼r Zwischenrechnungen verwendet werden kann
	Indem man die Eingabe nur lesbar macht
	Man kann dann die Eingabe bei der Berechnung des Platzbedarfs vernachlÃ¤ssigen
	Eine Ã¤hnliche Argumentation fÃ¼hrt zu der EinschrÃ¤nkung der Ausgabe
	um sich Information zu "merken"
	dass die Kopfposition verwendet wird
	Durch die zusÃ¤tzliche EinschrÃ¤nkung einer mÃ¶glichen Kopfbewegung wird verhindert
	dass Ein- und Ausgabe bei der Speicherplatzanalyse nicht berÃ¼cksichtigt werden mÃ¼ssen
	Insgesamt stellen all diese EinschrÃ¤nkungen sicher
	Die vorgenommenen Modifikationen beeinflussen das Zeitverhalten der Maschine Ã¼brigens nur um einen konstanten Faktor und sind damit vernachlÃ¤ssigbar. [Bearbeiten]
Verwendung und Rechtfertigung der O-Notation
	Bei der Untersuchung von GrÃ¶ÃŸenordnungen fÃ¼r AufwÃ¤nde wird in der KomplexitÃ¤tstheorie ausgiebig von der O-Notation Gebrauch gemacht
	Dabei werden lineare Faktoren und Konstanten aus der Betrachtung ausgeblendet
	Diese Vorgehensweise mag zunÃ¤chst Ã¼berraschen
	wÃ¤re doch fÃ¼r den Praktiker hÃ¤ufig bereits eine Halbierung der AufwÃ¤nde von hoher Bedeutung. Der Standpunkt der KomplexitÃ¤tstheorie lÃ¤sst sich theoretisch mit einer Technik rechtfertigen
	die man als lineares Beschleunigen oder auch Speedup-Theorem bezeichnet. (Wir beschrÃ¤nken uns hier auf das Zeitverhalten
	eine neue Turingmaschine konstruieren lÃ¤sst
	die ein Problem in O(f) Zeit berechnet
	Analoge Beweise kann man auch fÃ¼r den Speicherbedarf oder andere Ressourcen fÃ¼hren.) Das Speedup-Theorem besagt vereinfachend
	dass sich zu jeder Turingmaschine
	die das Problem in O(f') Zeit mit f' = ÎµÂ·f (0 < Îµ) berechnet
	als dass sich jede Turingmaschine
	die ein bestimmtes Problem lÃ¶st
	um einen beliebigen linearen Faktor beschleunigen lÃ¤sst
	Das bedeutet nichts anderes
	Der Preis fÃ¼r diese Beschleunigung besteht in einer stark vergrÃ¶ÃŸerten Zustandsmenge der verwendeten Turingmaschine (letztlich also "Hardware"). Die Beschleunigung wird unabhÃ¤ngig von der ProblemgrÃ¶ÃŸe erreicht
	Es wÃ¼rde daher keinen Sinn machen
	lineare Faktoren bei der Betrachtung von Problemen zu berÃ¼cksichtigen - solche Faktoren lieÃŸen sich durch eine geeignete Maschinendefinition ohnehin beseitigen
	Umgekehrt wÃ¼sste man garnicht
	ob sich der jeweils angegebene Faktor nun durch das Problem selbst oder durch die jeweils gewÃ¤hlte Maschinendefinition ergeben hat
	die sich in der O-Notation ausdrÃ¼ckt
	hat daher nicht nur praktische GrÃ¼nde
	sie vermeidet auch VerfÃ¤lschungen im Rahmen komplexitÃ¤tstheoretischer Betrachtungen. [Bearbeiten]
	Die VernachlÃ¤ssigung linearer Faktoren
Bildung von KomplexitÃ¤tsklassen
	Ein wesentliches Resultat der KomplexitÃ¤tstheorie ist die Bildung von KomplexitÃ¤tsklassen und Aussagen Ã¼ber deren wechselseitige Beziehungen. [Bearbeiten]
EinflussgrÃ¶ÃŸen bei der Bildung von KomplexitÃ¤tsklassen
	Eine Reihe von Faktoren nehmen auf die Bildung von KomplexitÃ¤tsklassen Einfluss
	Registermaschine usw.)
	Die wichtigsten sind die folgenden: Das zugrundeliegende Berechnungsmodell (Turingmaschine
	Der verwendete Berechnungsmodus (deterministisch
	probabilistisch usw.)
	nichtdeterministisch
	Platz
	Prozessoren usw.)
	Die betrachtete Berechnungsressource (Zeit
	Das angenommene KostenmaÃŸ (uniform
	logarithmisch)
	Die eingesetzte Schrankenfunktion. [Bearbeiten]
Anforderungen an Schrankenfunktionen
	Zur Angabe oder Definition von KomplexitÃ¤tsklassen verwendet man Schrankenfunktionen
	so meint man damit die Klasse aller Probleme
	Schreibt man beispielsweise DTIME(f)
	die auf einer deterministischen Turingmaschine in der Zeit O(f) entschieden werden kÃ¶nnen. f ist dabei eine Schrankenfunktion
	Um als Schrankenfunktion fÃ¼r komplexitÃ¤tstheoretische Analysen eingesetzt werden zu kÃ¶nnen
	Speicher usw. werden als natÃ¼rliche Zahlen berechnet). f(n+1) â‰¥ f(n) (monotones Wachstum)
	sollte die Funktion mindestens die folgenden Anforderungen erfÃ¼llen: f: N -> N (Schrittzahl
	bezeichnet man auch als echte KomplexitÃ¤tsfunktion
	Die Funktion f muss selbst in Zeit O(f) und mit Raum O(f) berechenbar sein. Eine Funktion
	die diesen Anforderungen genÃ¼gt
	Der Sinn der Anforderungen ist zum Teil technischer Natur
	Die Schrankenfunktion kann selbst auf konstruktive Art (z.B. als Turingmaschine) in Beweise einflieÃŸen und sollte sich daher fÃ¼r diese Zwecke "gutartig" verhalten
	die Logarithmusfunktion
	um nicht zu widersprÃ¼chlichen Ergebnissen zu gelangen. Die meisten "natÃ¼rlichen" Funktionen entsprechen den oben genannten EinschrÃ¤nkungen
	An dieser Stelle soll nur bewusst gemacht werden
	dass bei der Wahl der Schrankenfunktion eine gewisse Vorsicht walten muss
	die Wurzelfunktion
	so etwa die konstante Funktion
	Polynome
	die Exponentialfunktion sowie alle Kombinationen dieser Funktionen
	Es folgt eine Ãœbersicht der wichtigsten Schrankenfunktionen mit der jeweils Ã¼blichen Sprechweise
	Die Angabe erfolgt wie Ã¼blich in O-Notation. Die wichtigsten Schrankenfunktionen konstant O(1) logarithmisch O(log n) polylogarithmisch O(logk n) fÃ¼r k â‰¥ 1 linear O(n) n-log-n O(n log n) quadratisch O(nÂ²) polynomiell O(nk) fÃ¼r k â‰¥ 1 exponentiell O(dn) fÃ¼r d â‰¥ 1 [Bearbeiten]
HierarchiesÃ¤tze
	dass durch zusÃ¤tzlich bereitgestellte Ressourcen tatsÃ¤chlich mehr Probleme gelÃ¶st werden kÃ¶nnen
	FÃ¼r die gebildeten Klassen mÃ¶chte man mÃ¶glichst beweisen
	Diese Beweise bezeichnet man als HierarchiesÃ¤tze
	da sie auf den Klassen der jeweiligen Ressource eine Hierarchie induzieren
	Es gibt also Klassen
	die in eine echte Teilmengenbeziehung gesetzt werden kÃ¶nnen
	Wenn man solche echten Teilmengenbeziehungen ermittelt hat
	um damit eine grÃ¶ÃŸere Zahl von Problemen berechnen zu kÃ¶nnen
	wie groÃŸ die ErhÃ¶hung einer Ressource sein muss
	lassen sich auch Aussagen darÃ¼ber treffen
	Von besonderem Interesse sind dabei wiederum die Ressourcen Zeit und Raum
	Die induzierten Hierarchien bezeichnet man auch als Zeithierarchie und Raumhierarchie
	Die HierarchiesÃ¤tze bilden letztlich das Fundament fÃ¼r die Separierung von KomplexitÃ¤tsklassen
	Sie waren daher auch eines der frÃ¼hesten Ergebnisse der KomplexitÃ¤tstheorie
	Ohne die HierarchiesÃ¤tze mÃ¼sste fÃ¼r die Beziehungen der unterschiedlichen Klassen statt einer âŠ‚-Hierarchie eine âŠ†-Hierarchie angenommen werden
	Es bliebe dann zu befÃ¼rchten
	dass die gesamte Hierarchie zu einer einzigen Klasse kollabiert
	TatsÃ¤chlich muss ergÃ¤nzt werden
	dass alle HierarchiesÃ¤tze auf diversen Voraussetzungen beruhen
	Eine dieser Voraussetzungen ist etwa
	dass die oben genannten Anforderungen an echte KomplexitÃ¤tsfunktionen erfÃ¼llt werden
	Ohne die Einhaltung dieser Anforderungen bricht tatsÃ¤chlich die gesamte Klassenhierarchie in sich zusammen. Exkurs: Derartige Probleme gibt es beispielsweise im Bereich der probabilistischen KomplexitÃ¤tsklassen
	dass die KomplexitÃ¤tsklassen nicht mehr aufzÃ¤hlbar sind
	so resultiert daraus u.a.
	SchrÃ¤nkt man hier - wie fÃ¼r praktisch verwendbare probabilistische Algorithmen erforderlich - die Fehlerwahrscheinlichkeit ein
	Dies ist aber fÃ¼r alle Separationsverfahren eine Voraussetzung
	Als Ergebnis lassen sich Polynomzeitalgorithmen plÃ¶tzlich durch Linearzeitalgorithmen ersetzen
	Das Beispiel zeigt
	wie sensibel das Geflecht aus Voraussetzungen und den abgeleiteten SÃ¤tzen insgesamt ist. [Bearbeiten]
Zeithierarchiesatz
	dass man die Zeitressource um einen Faktor <math>log^{2}(f(n))<math> erhÃ¶hen muss
	um auf einer deterministischen Turingmaschine mehr Probleme lÃ¶sen zu kÃ¶nnen
	Der Zeithierarchiesatz besagt: <math>DTIME(f(n)) subset DTIME(f(n) sdot log^{2}(f(n)))<math> Dies bedeutet also
	Eine Ã¤hnliche Beziehung lÃ¤sst sich fÃ¼r nichtdeterministische Turingmaschinen finden. [Bearbeiten]
Raumhierarchiesatz
	Der Raumhierarchiesatz besagt: <math>DSPACE(f(n)) subset DSPACE(f(n) sdot log(f(n)))<math> Die Aussage ist analog zum Zeithierarchiesatz
	um eine grÃ¶ÃŸere Klasse zu bilden
	Man erkennt jedoch
	dass im Vergleich zur Zeit bereits eine geringere Steigerung des Raumes ausreicht (Faktor <math>log(f(n))<math> im Vergleich zu <math>log^{2}(f(n))<math>)
	verhÃ¤lt sich doch der Raum insgesamt aufgrund seiner Wiederverwendbarkeit (alte Zwischenergebnisse kÃ¶nnen Ã¼berschrieben werden) gutmÃ¼tiger. [Bearbeiten]
	Dies entspricht auch einer intuitiven Erwartung
WofÃ¼r die HierarchiesÃ¤tze nicht gelten
	Die HierarchiesÃ¤tze beziehen sich ausschlieÃŸlich auf den jeweils gleichen Berechnungsmodus und eine einzelne Ressource
	also z.B. auf die Ressource Zeit auf einem deterministischen Maschinenmodell
	wie sich etwa Raum- und Zeitklassen zueinander verhalten oder in welchem VerhÃ¤ltnis deterministische oder nichtdeterministische Klassen zueinander stehen
	Es wird jedoch keine Aussage darÃ¼ber getroffen
	Dennoch gibt es derartige ZusammenhÃ¤nge
	Sie werden in den Abschnitten Beziehungen zwischen Raum- und Zeitklassen und Beziehungen zwischen deterministischen und nichtdeterministischen Klassen behandelt. [Bearbeiten]
Wichtige Zeitklassen
	DTIME(f): Allgemeine Schreibweise fÃ¼r deterministische Zeitklassen
	P: Deterministisch in Polynomialzeit entscheidbare Sprachen
	EXPTIME: Deterministisch in Exponentialzeit entscheidbare Sprachen
	NTIME(f): Allgemeine Schreibweise fÃ¼r nichtdeterministische Zeitklassen
	NP: Nichtdeterministisch in Polynomialzeit entscheidbare Sprachen
	NEXPTIME: Nichtdeterministisch in Exponentialzeit entscheidbare Sprachen
	NC: Parallel in polylogarithmischer Zeit berechenbare Funktionen. [Bearbeiten]
Wichtige Raumklassen
	DSPACE(f): Allgemeine Schreibweise fÃ¼r deterministische Raumklassen
	L: Deterministisch mit logarithmischem Raum entscheidbare Sprachen
	PSPACE: Deterministisch in mit polynomialem Raum entscheidbare Sprachen
	NSPACE(f): Allgemeine Schreibweise fÃ¼r nichtdeterministische Zeitklassen
	NL: Nichtdeterministisch mit logarithmischem Raum entscheidbare Sprachen. [Bearbeiten]
Komplementbildungen
	indem man die Menge der nicht erkannten Worte als Menge der erkannten Worte definiert und umgekehrt
	FÃ¼r jede KomplexitÃ¤tsklasse lÃ¤sst sich das Komplement bilden
	Der neu gebildeten Komplementklasse stellt man das PrÃ¤fix co vor
	so heiÃŸt ihr Komplement coK
	HeiÃŸt also die Ausgangsklasse K
	FÃ¼r deterministische Maschinen gilt hÃ¤ufig K = coK
	da in der Ãœbergangsfunktion einfach nur die ÃœbergÃ¤nge zu akzeptierenden ZustÃ¤nden durch ÃœbergÃ¤nge zu verwerfenden ZustÃ¤nden ausgetauscht werden mÃ¼ssen und umgekehrt
	FÃ¼r andere Berechnungsmodi gilt dies jedoch nicht
	da hier die Akzeptierung anders definiert ist
	Beispielsweise ist bislang unbekannt
	ob NP = coNP gilt
	P = coP ist jedoch bewiesen. [Bearbeiten]
Sprachen und KomplexitÃ¤tsklassen
	Der folgende Baum gibt einen - recht groben - Ãœberblick Ã¼ber die ZusammenhÃ¤nge zwischen Sprachen der Chomsky-Hierarchie und verschiedenen KomplexitÃ¤tsklassen. Entscheidungsproblem Typ 0 (rekursiv aufzÃ¤hlbar) Unentscheidbar Entscheidbar EXPSPACE EXPTIME PSPACE Typ 1 (kontextsensitiv) PSPACE-vollstÃ¤ndig CoNP NP BPP BQP NP-vollstÃ¤ndig P NC P-vollstÃ¤ndig Typ 2 (kontextfrei) Typ 3 (regulÃ¤r) [Bearbeiten]
Anwendungsbereiche
	Ein wichtiger Anwendungsbereich der KomplexitÃ¤tstheorie ist die Kryptographie
	Auch in der Informationstheorie findet sie Andwendung
	wobei dort die KomplexitÃ¤t einer Nachricht als MaÃŸ fÃ¼r ihren Informationsgehalt bestimmt werden soll: siehe auch algorithmischer Informationsgehalt und algorithmische Tiefe
	Vorlage:Navigationsleiste KomplexitÃ¤tsklassen el:Î˜ÎµÏ‰Ï?Î¯Î± Î Î¿Î»Ï…Ï€Î»Î¿ÎºÏŒÏ„Î·Ï„Î±Ï‚ en:Computational complexity theory es:Complejidad computacional fr:ComplexitÃ© algorithmique ja:è¨ˆç®—è¤‡é›‘æ€§ç?†è«– pl:ZÅ‚oÅ¼onoÅ›Ä‡ obliczeniowa sv:Komplexitetsteori zh:è¨ˆç®—è¤‡é›œæ€§ç?†è«–

[X] Schliessen

Dieser Artikel basiert auf dem Artikel KomplexitÃ¤tstheorie aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.

Portsmouth (Rhode Island) San Juan Islands Klavier TragflÃ¤che Auftrieb Trockeneis Brechung 20. April

[Zurück ]

Inhalt Glossar:

Diese Seite einem Freund, Kollegen oder Bekannten weiterempfehlen? Hier klicken!

Allgemein

Probleme aus Sicht der KomplexitÃ¤tstheorie

Probleme als formale Sprachen

Probleminstanzen

ProblemreprÃ¤sentationen

Entscheidungsprobleme

ProblemgrÃ¶ÃŸen

Best, worst und average case fÃ¼r ProblemgrÃ¶ÃŸen

Untere und obere Schranken fÃ¼r Probleme

Maschinenmodelle in der KomplexitÃ¤tstheorie

Kostenfunktionen

KostenmaÃŸe

Maschinenmodelle und Probleme

HÃ¤ufig eingesetzte Maschinenmodelle

Modellmodifikationen fÃ¼r Speicherplatzanalysen

Verwendung und Rechtfertigung der O-Notation

Bildung von KomplexitÃ¤tsklassen

EinflussgrÃ¶ÃŸen bei der Bildung von KomplexitÃ¤tsklassen

Anforderungen an Schrankenfunktionen

HierarchiesÃ¤tze

Zeithierarchiesatz

Raumhierarchiesatz

WofÃ¼r die HierarchiesÃ¤tze nicht gelten

Wichtige Zeitklassen

Wichtige Raumklassen

Komplementbildungen

Sprachen und KomplexitÃ¤tsklassen

Anwendungsbereiche