Schneller Zugriff als Browser!
27 Beziehungen: Alternierende Turingmaschine, Determinismus, Einwegfunktion, Entscheidbar, Erfüllbarkeitsproblem der Aussagenlogik, Erfüllbarkeitsproblem für quantifizierte boolesche Formeln, Interaktives Beweissystem, Johan Håstad, Komplexitätsklasse, Komplexitätstheorie, Kontextsensitive Grammatik, Mengenlehre, NC (Komplexitätsklasse), Nichtdeterministische Turingmaschine, NP (Komplexitätsklasse), Null-Wissen-Beweis, Oded Goldreich, P (Komplexitätsklasse), Phillip Rogaway, Platzkomplexität, Polynom, Polynomialzeitreduktion, Satz von Savitch, Schwere und Vollständigkeit (theoretische Informatik), Shafrira Goldwasser, Silvio Micali, 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!!: PSPACE und Alternierende Turingmaschine · Mehr sehen »
Determinismus
Der Determinismus (von ‚festlegen‘, ‚Grenzen setzen‘, ‚begrenzen‘) ist die Auffassung, dass alle – insbesondere auch zukünftige – Ereignisse durch Vorbedingungen eindeutig festgelegt sind.
Neu!!: PSPACE und Determinismus · Mehr sehen »
Einwegfunktion
In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist.
Neu!!: PSPACE und Einwegfunktion · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: PSPACE und Entscheidbar · Mehr sehen »
Erfüllbarkeitsproblem der Aussagenlogik
Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von ‚ Erfüllbarkeit‘) ist ein Entscheidungsproblem der theoretischen Informatik.
Neu!!: PSPACE und Erfüllbarkeitsproblem der Aussagenlogik · 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!!: PSPACE und Erfüllbarkeitsproblem für quantifizierte boolesche Formeln · Mehr sehen »
Interaktives Beweissystem
Ein interaktives Beweissystem ist ein Begriff aus der Komplexitätstheorie.
Neu!!: PSPACE und Interaktives Beweissystem · Mehr sehen »
Johan Håstad
Johan Torkel Håstad (* 19. November 1960) ist ein schwedischer Informatiker.
Neu!!: PSPACE und Johan Håstad · 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!!: PSPACE und Komplexitätsklasse · Mehr sehen »
Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen.
Neu!!: PSPACE und Komplexitätstheorie · Mehr sehen »
Kontextsensitive Grammatik
Die kontextsensitiven Grammatiken (kurz CSG, von engl. context-sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie.
Neu!!: PSPACE und Kontextsensitive Grammatik · Mehr sehen »
Mengenlehre
Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das sich mit der Untersuchung von Mengen, also von Zusammenfassungen von Objekten, beschäftigt.
Neu!!: PSPACE und Mengenlehre · Mehr sehen »
NC (Komplexitätsklasse)
NC steht in der Informatik als Abkürzung für Nick's Class (nach Nick Pippenger), die Komplexitätsklasse der parallel effizient lösbaren Entscheidungsprobleme.
Neu!!: PSPACE und NC (Komplexitätsklasse) · Mehr sehen »
Nichtdeterministische Turingmaschine
Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
Neu!!: PSPACE und Nichtdeterministische Turingmaschine · 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!!: PSPACE und NP (Komplexitätsklasse) · Mehr sehen »
Null-Wissen-Beweis
Ein Null-Wissen-Beweis kann mit hoher Wahrscheinlichkeit nachweisen, dass man ein Geheimnis weiß, ohne das Geheimnis zu verraten.
Neu!!: PSPACE und Null-Wissen-Beweis · Mehr sehen »
Oded Goldreich
Goldreich, 2006 Oded Goldreich (* 4. Februar 1957 in Tel Aviv) ist ein israelischer Mathematiker und Informatiker.
Neu!!: PSPACE und Oded Goldreich · 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!!: PSPACE und P (Komplexitätsklasse) · Mehr sehen »
Phillip Rogaway
Phillip Rogaway ist ein US-amerikanischer Informatiker, der sich mit Kryptographie befasst.
Neu!!: PSPACE und Phillip Rogaway · Mehr sehen »
Platzkomplexität
Unter der Platzkomplexität eines Problems versteht man den (minimalen) Bedarf an Speicherplatz eines Algorithmus zur Lösung dieses Problems, in Abhängigkeit von der Länge der Eingabe.
Neu!!: PSPACE und Platzkomplexität · Mehr sehen »
Polynom
Ein Polynom ist ein algebraischer Term, der sich als Summe von Vielfachen von Potenzen einer Variablen bzw.
Neu!!: PSPACE und Polynom · Mehr sehen »
Polynomialzeitreduktion
Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik.
Neu!!: PSPACE und Polynomialzeitreduktion · Mehr sehen »
Satz von Savitch
Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde.
Neu!!: PSPACE und Satz von Savitch · Mehr sehen »
Schwere und Vollständigkeit (theoretische Informatik)
In der theoretischen Informatik – insbesondere in der Berechenbarkeits- und der Komplexitätstheorie – bezeichnet die Schwere (Übersetzung von engl. hardness dt. „Schwierigkeit“) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse.
Neu!!: PSPACE und Schwere und Vollständigkeit (theoretische Informatik) · Mehr sehen »
Shafrira Goldwasser
Shafrira Goldwasser Shafrira „Shafi“ Goldwasser (* 1958 in New York City) ist eine US-amerikanische Informatikerin.
Neu!!: PSPACE und Shafrira Goldwasser · Mehr sehen »
Silvio Micali
Silvio Micali Silvio Micali (* 13. Oktober 1954 in Palermo) ist ein italienischstämmiger US-amerikanischer Informatiker.
Neu!!: PSPACE und Silvio Micali · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: PSPACE und Turingmaschine · Mehr sehen »
Leitet hier um:
NPSPACE, PSPACE-Vollständigkeit.
