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

NP-Äquivalenz

Index NP-Äquivalenz

NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik.

13 Beziehungen: David Stifler Johnson, Entscheidbar, Informatik, Komplexitätstheorie, Makrokosmos, Michael Garey, NP (Komplexitätsklasse), NP-leicht, NP-Schwere, NP-Vollständigkeit, P-NP-Problem, Polynomialzeit, Suchproblem.

David Stifler Johnson

David Stifler Johnson (* 9. Dezember 1945 in Washington, D.C.; † 8. März 2016) war ein US-amerikanischer Informatiker.

Neu!!: NP-Äquivalenz und David Stifler Johnson · 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!!: NP-Äquivalenz und Entscheidbar · Mehr sehen »

Informatik

Lambda lc.svg Sorting quicksort anim frame.svg Utah teapot simple 2.png 3-Tasten-Maus Microsoft.jpg Bei der Informatik handelt es sich um die Wissenschaft von der systematischen Darstellung, Speicherung, Verarbeitung und Übertragung von Daten, wobei besonders die automatische Verarbeitung mit Computern betrachtet wird.

Neu!!: NP-Äquivalenz und Informatik · 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!!: NP-Äquivalenz und Komplexitätstheorie · Mehr sehen »

Makrokosmos

Makrokosmos („große Welt“, von griechisch makrós „groß“ und kósmos „Welt“, lateinisch macrocosmus oder maior mundus) ist der Gegenbegriff zu Mikrokosmos („kleine Welt“).

Neu!!: NP-Äquivalenz und Makrokosmos · Mehr sehen »

Michael Garey

Michael Randolph Garey (* 19. November 1945 in Manitowoc, Wisconsin) ist ein US-amerikanischer Informatiker.

Neu!!: NP-Äquivalenz und Michael Garey · 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!!: NP-Äquivalenz und NP (Komplexitätsklasse) · Mehr sehen »

NP-leicht

In der Komplexitätstheorie bezeichnet die Komplexitätsklasse NP-leicht (auch FPNP, wobei FP für funktionale Polynomialzeit steht) die Menge aller Funktionen, die in polynomieller Zeit durch eine deterministische Turingmaschine mit Hilfe einer Orakel-Turingmaschine für ein Entscheidungsproblem aus der Klasse NP berechnet werden können.

Neu!!: NP-Äquivalenz und NP-leicht · 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!!: NP-Äquivalenz 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!!: NP-Äquivalenz und NP-Vollständigkeit · 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!!: NP-Äquivalenz und P-NP-Problem · Mehr sehen »

Polynomialzeit

In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn es mit einer deterministischen Rechenmaschine in einer Rechenzeit lösbar ist, die mit der Problemgröße nicht stärker als gemäß einer Polynomfunktion wächst.

Neu!!: NP-Äquivalenz und Polynomialzeit · Mehr sehen »

Suchproblem

Als Suchproblem bezeichnet man in der theoretischen Informatik ein Problem, bei dem zu einer gegebenen Eingabe eine bestmögliche Lösung gesucht ist.

Neu!!: NP-Äquivalenz und Suchproblem · Mehr sehen »

Leitet hier um:

NP-äquivalent.

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »