Schneller Zugriff als Browser!
41 Beziehungen: Automat (Informatik), BPP (Komplexitätsklasse), BQP, Co-NP, Determinismus (Algorithmus), DSPACE, DTIME, E (Komplexitätsklasse), Erreichbarkeitsproblem in Graphen, EXPSPACE, EXPTIME, FP (Komplexitätsklasse), Komplexitätsklasse, Komplexitätstheorie, L (Komplexitätsklasse), Landau-Symbole, NC (Komplexitätsklasse), NEXPTIME, Nichtdeterministische Turingmaschine, NL (Komplexitätsklasse), NP (Komplexitätsklasse), NP-Schwere, NP-Vollständigkeit, NSPACE, NTIME, P (Komplexitätsklasse), Parametrisierter Algorithmus, Platzkomplexität, Polynom, Polynomialzeithierarchie, Probabilistische Polynomialzeit, Probabilistische Turingmaschine, Problemkern, PSPACE, Quantencomputer, RL (Komplexitätsklasse), RP (Komplexitätsklasse), Sharp-P, Turingmaschine, Zeitkomplexität, ZPP (Komplexitätsklasse).
Automat (Informatik)
Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.
Neu!!: Liste von Komplexitätsklassen und Automat (Informatik) · Mehr sehen »
BPP (Komplexitätsklasse)
In der Komplexitätstheorie steht BPP (englische Abkürzung für bounded error probabilistic polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen.
Neu!!: Liste von Komplexitätsklassen und BPP (Komplexitätsklasse) · Mehr sehen »
BQP
Die Lage von BQP relativ zu anderen ProblemklassenMichael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. Die Komplexitätsklasse BQP (von) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.
Neu!!: Liste von Komplexitätsklassen und BQP · Mehr sehen »
Co-NP
In der Komplexitätstheorie bezeichnet Co-NP eine Komplexitätsklasse.
Neu!!: Liste von Komplexitätsklassen und Co-NP · Mehr sehen »
Determinismus (Algorithmus)
Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.
Neu!!: Liste von Komplexitätsklassen und Determinismus (Algorithmus) · Mehr sehen »
DSPACE
Der Begriff DSPACE stammt aus der Komplexitätstheorie in der theoretischen Informatik.
Neu!!: Liste von Komplexitätsklassen und DSPACE · Mehr sehen »
DTIME
In der Komplexitätstheorie steht DTIME(f) oder auch kurz TIME(f) für die Menge der Zeitkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine.
Neu!!: Liste von Komplexitätsklassen und DTIME · Mehr sehen »
E (Komplexitätsklasse)
Die Komplexitätsklasse \mathbf E ist die Klasse aller Sprachen, die sich von einer deterministischen Turingmaschine in exponentieller Zeit mit linearem Exponenten lösen lassen.
Neu!!: Liste von Komplexitätsklassen und E (Komplexitätsklasse) · Mehr sehen »
Erreichbarkeitsproblem in Graphen
Das Erreichbarkeitsproblem in Graphen (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt.
Neu!!: Liste von Komplexitätsklassen und Erreichbarkeitsproblem in Graphen · Mehr sehen »
EXPSPACE
In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch \mathcal O\left(2^\right) Platz entschieden werden können, wobei p(n) ein beliebiges Polynom ist.
Neu!!: Liste von Komplexitätsklassen und EXPSPACE · Mehr sehen »
EXPTIME
Zusammenhang mit anderen Komplexitätsklassen In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine (DTM) in durch \mathcal O\left(2^\right) beschränkter Zeit entschieden werden können.
Neu!!: Liste von Komplexitätsklassen und EXPTIME · Mehr sehen »
FP (Komplexitätsklasse)
In der theoretischen Informatik, speziell der Komplexitätstheorie, beschreibt die Klasse FP die Menge aller Suchprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können (englisch function polynomial time, daher auch die Abkürzung).
Neu!!: Liste von Komplexitätsklassen und FP (Komplexitätsklasse) · 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!!: Liste von Komplexitätsklassen 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!!: Liste von Komplexitätsklassen und Komplexitätstheorie · Mehr sehen »
L (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können.
Neu!!: Liste von Komplexitätsklassen und L (Komplexitätsklasse) · Mehr sehen »
Landau-Symbole
Landau-Symbole (auch O-Notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.
Neu!!: Liste von Komplexitätsklassen und Landau-Symbole · 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!!: Liste von Komplexitätsklassen und NC (Komplexitätsklasse) · Mehr sehen »
NEXPTIME
In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch \mathcal(2^) (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können.
Neu!!: Liste von Komplexitätsklassen und NEXPTIME · Mehr sehen »
Nichtdeterministische Turingmaschine
Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
Neu!!: Liste von Komplexitätsklassen und Nichtdeterministische Turingmaschine · Mehr sehen »
NL (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können.
Neu!!: Liste von Komplexitätsklassen und NL (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!!: Liste von Komplexitätsklassen und NP (Komplexitätsklasse) · Mehr sehen »
NP-Schwere
NP-vollständigen Probleme. Zu beachten ist, dass auf der rechten Seite die leere Sprache und ihr Komplement außen vor gelassen werden (beide sind zwar in P und NP, aber nicht NP-schwer). NP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP.
Neu!!: Liste von Komplexitätsklassen und NP-Schwere · Mehr sehen »
NP-Vollständigkeit
NP-schweren und NP-vollständigen Probleme. In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist.
Neu!!: Liste von Komplexitätsklassen und NP-Vollständigkeit · Mehr sehen »
NSPACE
NSPACE (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik.
Neu!!: Liste von Komplexitätsklassen und NSPACE · Mehr sehen »
NTIME
In der Komplexitätstheorie steht NTIME(f) für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können.
Neu!!: Liste von Komplexitätsklassen und NTIME · 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!!: Liste von Komplexitätsklassen und P (Komplexitätsklasse) · Mehr sehen »
Parametrisierter Algorithmus
Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollständigen Problemen effizient zu lösen sind.
Neu!!: Liste von Komplexitätsklassen und Parametrisierter Algorithmus · 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!!: Liste von Komplexitätsklassen und Platzkomplexität · Mehr sehen »
Polynom
Ein Polynom ist ein algebraischer Term, der sich als Summe von Vielfachen von Potenzen einer Variablen bzw.
Neu!!: Liste von Komplexitätsklassen und Polynom · Mehr sehen »
Polynomialzeithierarchie
Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie) ist die vermutete Struktur von Komplexitätsklassen zwischen NP und PSPACE.
Neu!!: Liste von Komplexitätsklassen und Polynomialzeithierarchie · Mehr sehen »
Probabilistische Polynomialzeit
In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die in von einer probabilistischen Turingmaschine in Polynomialzeit lösbar ist und die Antwort in mindestens der Hälfte der Fälle richtig ist.
Neu!!: Liste von Komplexitätsklassen und Probabilistische Polynomialzeit · Mehr sehen »
Probabilistische Turingmaschine
Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik.
Neu!!: Liste von Komplexitätsklassen und Probabilistische Turingmaschine · Mehr sehen »
Problemkern
In der theoretischen Informatik bezeichnet der Problemkern (engl. problemkernel) den algorithmisch „schwierig“ entscheidbaren Teil einer Instanz eines NP-Schweren Problems.
Neu!!: Liste von Komplexitätsklassen und Problemkern · 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!!: Liste von Komplexitätsklassen und PSPACE · Mehr sehen »
Quantencomputer
Ein Quantenprozessor bzw.
Neu!!: Liste von Komplexitätsklassen und Quantencomputer · Mehr sehen »
RL (Komplexitätsklasse)
In der Komplexitätstheorie ist RL die Klasse der Entscheidungsprobleme, die von einer probabilistischen Turingmaschine auf logarithmischen Platz mit beschränkter einseitiger Irrtumswahrscheinlichkeit lösbar sind.
Neu!!: Liste von Komplexitätsklassen und RL (Komplexitätsklasse) · Mehr sehen »
RP (Komplexitätsklasse)
RP im Verhältnis zu anderen probabilistischen Komplexitätsklassen RP (manchmal auch nur mit R bezeichnet) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe eine Fehlerwahrscheinlichkeit von höchstens 1/2 hat.
Neu!!: Liste von Komplexitätsklassen und RP (Komplexitätsklasse) · Mehr sehen »
Sharp-P
Die Komplexitätsklasse #P (englische Aussprache Sharp-P oder Number-P) ist eine Klasse von sogenannten Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die Entscheidbar behandeln).
Neu!!: Liste von Komplexitätsklassen und Sharp-P · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: Liste von Komplexitätsklassen und Turingmaschine · Mehr sehen »
Zeitkomplexität
Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe.
Neu!!: Liste von Komplexitätsklassen und Zeitkomplexität · Mehr sehen »
ZPP (Komplexitätsklasse)
Die Komplexitätsklasse ZPP beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine gibt, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt und folgende Eigenschaften besitzt.
Neu!!: Liste von Komplexitätsklassen und ZPP (Komplexitätsklasse) · Mehr sehen »
