Schneller Zugriff als Browser!
15 Beziehungen: Alternierende Turingmaschine, Bitkette, Christos Papadimitriou, Deskriptive Komplexitätstheorie, Erfüllbarkeitsproblem für quantifizierte boolesche Formeln, Formale Sprache, Komplexitätsklasse, NP (Komplexitätsklasse), Orakel-Turingmaschine, P (Komplexitätsklasse), P-NP-Problem, Prädikatenlogik zweiter Stufe, PSPACE, Sanjeev Arora, Turingmaschine.
Alternierende Turingmaschine
In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert.
Neu!!: Polynomialzeithierarchie und Alternierende Turingmaschine · Mehr sehen »
Bitkette
In der Informatik ist eine Bitkette (auch Bitstring oder je nach Dimension Bitvektor bzw. Bitarray) eine (endliche) Folge von Zeichen aus dem kleinsten interessanten Alphabet Σ; dieses besteht aus zwei Zeichen, den Bits: Σ.
Neu!!: Polynomialzeithierarchie und Bitkette · Mehr sehen »
Christos Papadimitriou
Christos Charilaos Papadimitriou (* 1949 in Athen) ist ein griechischer Informatiker.
Neu!!: Polynomialzeithierarchie und Christos Papadimitriou · Mehr sehen »
Deskriptive Komplexitätstheorie
Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht.
Neu!!: Polynomialzeithierarchie und Deskriptive Komplexitätstheorie · Mehr sehen »
Erfüllbarkeitsproblem für quantifizierte boolesche Formeln
Das Erfüllbarkeitsproblem für quantifizierte boolesche Formeln ist eine Verallgemeinerung des Erfüllbarkeitsproblems der Aussagenlogik.
Neu!!: Polynomialzeithierarchie und Erfüllbarkeitsproblem für quantifizierte boolesche Formeln · Mehr sehen »
Formale Sprache
Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die Definition und Anwendung formaler Systeme im engeren Sinn und der Logik im weiteren, allgemeinen Sinn.
Neu!!: Polynomialzeithierarchie und Formale Sprache · Mehr sehen »
Komplexitätsklasse
Komplexitätsklassen In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands.
Neu!!: Polynomialzeithierarchie und Komplexitätsklasse · Mehr sehen »
NP (Komplexitätsklasse)
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.
Neu!!: Polynomialzeithierarchie und NP (Komplexitätsklasse) · Mehr sehen »
Orakel-Turingmaschine
Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist.
Neu!!: Polynomialzeithierarchie und Orakel-Turingmaschine · Mehr sehen »
P (Komplexitätsklasse)
In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind.
Neu!!: Polynomialzeithierarchie und P (Komplexitätsklasse) · Mehr sehen »
P-NP-Problem
Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik.
Neu!!: Polynomialzeithierarchie und P-NP-Problem · Mehr sehen »
Prädikatenlogik zweiter Stufe
Die Prädikatenlogik zweiter Stufe ist ein Teilgebiet der mathematischen Logik.
Neu!!: Polynomialzeithierarchie und Prädikatenlogik zweiter Stufe · Mehr sehen »
PSPACE
In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können.
Neu!!: Polynomialzeithierarchie und PSPACE · Mehr sehen »
Sanjeev Arora
Sanjeev Arora Sanjeev Arora (* Januar 1968 in JodhpurGemäß den biographischen Angaben auf seiner Homepage http://www.cs.princeton.edu/~arora/bio.html, Indien) ist ein US-amerikanischer Informatiker indischer Herkunft.
Neu!!: Polynomialzeithierarchie und Sanjeev Arora · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: Polynomialzeithierarchie und Turingmaschine · Mehr sehen »
Leitet hier um:
PH (Komplexitätsklasse), Polynomiale Hierarchie, Polynomielle Hierarchie.
