Logo
Unionpedia
Kommunikation
Jetzt bei Google Play
Neu! Laden Sie Unionpedia auf Ihrem Android™-Gerät herunter!
Installieren
Schneller Zugriff als Browser!
 

EXPTIME

Index 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.

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 »

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »