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

E (Komplexitätsklasse)

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

8 Beziehungen: Determinismus (Algorithmus), EXPTIME, Formale Sprache, Komplexitätsklasse, Komplexitätstheorie, Polynomialzeitreduktion, PSPACE, Turingmaschine.

Determinismus (Algorithmus)

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.

Neu!!: E (Komplexitätsklasse) und Determinismus (Algorithmus) · 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!!: E (Komplexitätsklasse) und EXPTIME · Mehr sehen »

Formale Sprache

Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu konkreten Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die mathematische Verwendung.

Neu!!: E (Komplexitätsklasse) und Formale Sprache · Mehr sehen »

Komplexitätsklasse

Komplexitätsklassen In der Komplexitätstheorie bezeichnet eine Komplexitätsklasse eine Menge von Problemen, welche sich in einem ressourcenbeschränkten Berechnungsmodell berechnen lassen.

Neu!!: E (Komplexitätsklasse) 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!!: E (Komplexitätsklasse) und Komplexitätstheorie · Mehr sehen »

Polynomialzeitreduktion

Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik.

Neu!!: E (Komplexitätsklasse) 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!!: E (Komplexitätsklasse) und PSPACE · Mehr sehen »

Turingmaschine

Eine Turingmaschine ist ein wichtiges Rechnermodell der theoretischen Informatik.

Neu!!: E (Komplexitätsklasse) und Turingmaschine · Mehr sehen »

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »