P (Komplexitätsklasse)

P (Komplexitätsklasse)

In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der "praktisch lösbaren" Probleme betrachtet.

Eine Verallgemeinerung von P ist die Klasse NP. Die Probleme aus NP sind zwar ebenfalls in Polynomialzeit entscheidbar, jedoch wird hierfür ein nicht realisierbares, nämlich nichtdeterministisches Maschinenmodell eingesetzt. P ist sicher eine Teilmenge von NP. Es gehört jedoch zu den wichtigsten ungelösten Fragen der theoretischen Informatik, ob P = NP gilt (siehe auch P-NP-Problem).

Inhaltsverzeichnis

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

LNLLOGCFLNC ⊆ P ⊆ NPPSPACEEXPTIMENEXPTIME
LOGCFL \not= PSPACE
P \not= EXPTIME

P-Vollständigkeit

Ein Entscheidungsproblem A heißt P-vollständig genau dann, wenn es in der Komplexitätsklasse P liegt und wenn jedes Problem in P durch eine Berechnung mit logarithmischen Platzverbrauch auf A reduziert werden kann, das heißt, wenn jede dieser Reduktionen in der Komplexitätsklasse L liegt (siehe auch: Vollständigkeit (Komplexitätstheorie)).

Ein bekanntes P-vollständiges Problem ist das Circuit-Value-Problem, bei dem bestimmt werden soll, ob das Ergebnis eines Booleschen Schaltkreises bei gegebener Eingabe einer gegebenen Ausgabe entspricht. Diese Probleme gehören zu den schwersten, noch effizient lösbaren Problemen aus der Komplexitätsklasse P. P-vollständige Probleme sind (momentan) schwer zu parallelisieren.

Bekannte Probleme in P

P-vollständige Probleme

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Komplexitätsklasse P — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • Komplexitätsklasse NP — NP (nichtdeterministisch polynomielle Zeit) ist eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge …   Deutsch Wikipedia

  • Komplexitätsklasse — Zusammenhang verschiedener Komplexitätsklassen Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine… …   Deutsch Wikipedia

  • Co-RP (Komplexitätsklasse) — co RP (random polynominal) bzw. co RP(ε(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1… …   Deutsch Wikipedia

  • BQP (Komplexitätsklasse) — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • SL (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. Um logarithmischen Platzverbrauch definieren zu können, muss… …   Deutsch Wikipedia

  • Co-NP (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. In der Komplexitätstheorie bezeichnet Co NP eine Komplexitätsklasse …   Deutsch Wikipedia

  • PH (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie)… …   Deutsch Wikipedia

  • NP (Komplexitätsklasse) — NP (nichtdeterministisch polynomielle Zeit) ist in der Informatik eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine… …   Deutsch Wikipedia

  • RP (Komplexitätsklasse) — RP (random polynomial) bzw. RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”