Komplexitätstheorie

Front Cover
Teubner, 1978 - Computers - 247 pages

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Berechenbarkeit
8
Nicht berechenbare Funktionen
56
Realistische Komplexitätsmaße
86
Copyright

4 other sections not shown

Common terms and phrases

0(s(n))-bandbeschränkte 1-Band-Turingmaschine akzeptiert Akzeptor Alphabet andernfalls angesetzt auf Eingabe Arbeitsband Aussage Axiome Bandinschrift bandkonstruierbar Bandverbrauch Befehl Beispiel Belegung ip beliebig benutzt berechenbare Funktion berechnet Berechnung Beweis von Lemma Beweis von Satz Beweissystem bin(i Binärdarstellung Block Boole'scher Ausdruck Boole'sches Prädikat definieren definiert Definition deterministische Eingabeband endliche Endzustand entscheidbar erzeugt falls Felder folgende folgt gerichteter Graph Gewinnstrategie gibt gilt gleich Gödelisierung Gödelnummer Graphen Großschritt hält Halteproblem heißt herleitbar höchstens Induktion Ingrad Inschrift von Band Inschrift von Spur irgendeine k-Bandmaschine Kante Klasse Knoten Kodierung Komplexität Komplexitätsmaß Komplexitätstheorie Konfiguration konjunktiver Normalform Konstante kontextsensitiven Sprachen Kopf Korollar Länge Lemma logarithmische Marken markiert Maschine Q Mathematik Menge nichtdeterministische NP-hart NP-vollständige OBdA polynomiell Pränex-Normalform primitiv rekursive Funktionen Programm Rechenverfahren Rechnung Register Registermaschine reguläre Rekursion rekursiv aufzählbar Schlußregeln Schranke Simulation simuliert Speicherplatz Sprache t(n)-zeitbeschränkte totale berechenbare Funktion Tupel turingberechenbar Turingmaschine Übungen uniform Variablen Verfahren y-rekursiv Zahlen Zeichen Zeichenreihe zeigen zeitbeschränkte Zeitintervall Zeitkomplexität Zustand Zustandsmenge zykelfreie