17 Beziehungen: Determinismus (Algorithmus), DTIME, Entscheidbar, Komplexitätsklasse, Komplexitätstheorie, NC (Komplexitätsklasse), NEXPTIME, NP (Komplexitätsklasse), NP-Vollständigkeit, P (Komplexitätsklasse), P-NP-Problem, Polynom, Polynomialzeitreduktion, PSPACE, Turingmaschine, Wortproblem, Zeitkomplexität.
Determinismus (Algorithmus)
Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.
Neu!!: EXPTIME und Determinismus (Algorithmus) · 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!!: EXPTIME und DTIME · 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!!: EXPTIME und Entscheidbar · 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!!: EXPTIME 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!!: EXPTIME und Komplexitätstheorie · 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!!: EXPTIME 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!!: EXPTIME und NEXPTIME · 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!!: EXPTIME und NP (Komplexitätsklasse) · 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!!: EXPTIME und NP-Vollständigkeit · 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!!: EXPTIME 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!!: EXPTIME und P-NP-Problem · Mehr sehen »
Polynom
Ein Polynom ist ein algebraischer Term, der sich als Summe von Vielfachen von Potenzen einer Variablen bzw.
Neu!!: EXPTIME und Polynom · Mehr sehen »
Polynomialzeitreduktion
Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik.
Neu!!: EXPTIME und Polynomialzeitreduktion · 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!!: EXPTIME und PSPACE · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: EXPTIME und Turingmaschine · Mehr sehen »
Wortproblem
Wortproblem steht für.
Neu!!: EXPTIME und Wortproblem · 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!!: EXPTIME und Zeitkomplexität · Mehr sehen »