In der Kompliziertheitstheorie ist der Begriff von P-complete Entscheidungsproblemen in der Analyse von beiden nützlich:

1. welche Probleme zu parallelize effektiv schwierig sind, und;
2. den Probleme schwierig sind, im beschränkten Raum zu lösen.

Formell ist ein Entscheidungsproblem P-complete (abgeschlossen für die Kompliziertheitsklasse P), wenn es in P ist, und dass jedes Problem in P darauf durch das Verwenden der passenden Verminderung reduziert werden kann.

Der spezifische Typ der verwendeten Verminderung ändert sich und kann den genauen Satz von Problemen betreffen. Wenn wir die NC Verminderungen, d. h. die Verminderungen verwenden, die in der polylogarithmischen Zeit auf einem parallelen Computer mit einer polynomischen Zahl von Verarbeitern funktionieren können, dann liegen alle P-complete Probleme außerhalb NC und können nicht effektiv parallelized, unter der unbewiesenen Annahme das NC  P so sein. Wenn wir die schwächere mit dem Klotzraumverminderung verwenden, bleibt das wahr, aber zusätzlich erfahren wir, dass alle P-complete Probleme außerhalb L unter der schwächeren unbewiesenen Annahme das L  P liegen. In diesem letzten Fall der Satz kann P-complete kleiner sein.

Motivation

Die Klasse P, normalerweise genommen, um aus allen "lenksamen" Problemen für einen folgenden Computer zu bestehen, enthält die Klasse NC, der aus jenen Problemen besteht, die auf einem parallelen Computer effizient gelöst werden können. Das ist, weil parallele Computer auf einer folgenden Maschine vorgetäuscht werden können.

Es ist ob NC = P nicht bekannt. Mit anderen Worten ist es nicht bekannt, ob es irgendwelche lenksamen Probleme gibt, die von Natur aus folgend sind. Da es weit vermutet wird, dass P NP nicht gleichkommt, so wird es weit vermutet, dass NC P nicht gleichkommt.

Ähnlich enthält die Klasse L alle Probleme, die durch einen folgenden Computer im logarithmischen Raum gelöst werden können. Solche Maschinen laufen in der polynomischen Zeit, weil sie eine polynomische Zahl von Konfigurationen haben können. Es wird das L  P verdächtigt; d. h. dass einige Probleme, die in der polynomischen Zeit auch gelöst werden können, mehr verlangen als logarithmischer Raum.

Ähnlich zum Gebrauch von NP-complete Problemen, den P = NP Frage zu analysieren, dienen die P-complete Probleme, angesehen als "wahrscheinlich nicht parallelizable" oder "wahrscheinlich von Natur aus folgenden" Probleme, auf eine ähnliche Weise, den NC = P Frage zu studieren. Wenn sie einen effizienten Weg zu parallelize findet, würde die Lösung eines P-complete Problems dem NC = P zeigen. Davon kann auch als die "Probleme gedacht werden, die superlogarithmischen Raum verlangen"; eine mit dem Klotzraumlösung eines P-complete Problems (die Definition verwendend, die auf den mit dem Klotzraumverminderungen gestützt ist), würde L = P einbeziehen.

Die Logik dahinter ist der Logik analog, dass eine polynomisch-malige Lösung eines NP-complete Problems P = NP beweisen würde: Wenn wir die NC Verminderung von einem Problem in P zu einem Problem A, und eine NC Lösung für A, dann NC = P haben. Ähnlich, wenn wir die mit dem Klotzraumverminderung von einem Problem in P zu einem Problem A, und eine mit dem Klotzraumlösung für A, dann L = P haben.

P-complete Probleme

Das grundlegendste P-complete Problem ist das: In Anbetracht einer Maschine von Turing, eines Eingangs für diese Maschine und einer Nummer T (geschrieben im unären), hinkt diese Maschine auf diesem Eingang innerhalb der ersten T-Schritte? Es ist klar, dass dieses Problem P-complete ist: Wenn wir parallelize eine allgemeine Simulation eines folgenden Computers können, dann werden wir zu parallelize jedes Programm fähig sein, das auf diesem Computer läuft. Wenn dieses Problem in NC ist, dann auch ist jedes andere Problem in P. Wenn die Zahl von Schritten in der Dualzahl geschrieben wird, ist das Problem EXPTIME-abgeschlossen.

Dieses Problem illustriert einen allgemeinen Trick in der Theorie der P-Vollständigkeit. Wir interessieren uns nicht wirklich dafür, ob ein Problem schnell auf einer parallelen Maschine behoben werden kann. Wir interessieren uns gerade dafür, ob eine parallele Maschine es viel schneller löst als eine folgende Maschine. Deshalb müssen wir das Problem umformulieren, so dass die folgende Version in P ist. Deshalb hat dieses Problem verlangt, dass T im unären geschrieben wurde. Wenn eine Nummer T als eine Binärzahl geschrieben wird (eine Reihe von n und Nullen, wo n = T loggen), dann kann der offensichtliche folgende Algorithmus 2 Zeit in Anspruch nehmen. Andererseits, wenn T als eine unäre Zahl geschrieben wird (eine Reihe von n, wo n = T), dann nimmt es nur n Zeit in Anspruch. Indem wir T im unären aber nicht binären schreiben, haben wir den offensichtlichen folgenden Algorithmus von der Exponentialzeit bis zur geradlinigen Zeit reduziert. Das stellt das folgende Problem in P. Dann wird es in NC sein, wenn, und nur wenn es parallelizable ist.

Wie man

bewiesen hat, sind viele andere Probleme P-complete gewesen, und werden deshalb weit geglaubt, von Natur aus folgend zu sein. Diese schließen die folgenden Probleme, entweder wie gegeben, oder in einer Entscheidungsproblem-Form ein:

• Circuit Value Problem (CVP) - Gegeben ein Stromkreis, die Eingänge zum Stromkreis, und ein Tor im Stromkreis, berechnet die Produktion dieses Tors
• Der eingeschränkte Fall von CVP - Wie CVP, außer jedem Tor hat zwei Eingänge und zwei Produktionen (F und Nicht F), jede andere Schicht ist gerade, UND Tore, der Rest ist ODER Tore (oder, gleichwertig alle Tore sind NAND Tore, oder alle Tore sind NOCH Tore), die Eingänge eines Tors kommen aus der sofort vorhergehenden Schicht
• Geradlinige Programmierung - Maximiert ein geradliniges Funktionsthema geradlinigen Ungleichheitseinschränkungen
• Die lexikografisch Erste Tiefe die Erste Suche, die - Gegeben ein Graph mit festen bestellten Angrenzen-Listen, und Knoten u und v Bestellt, ist Scheitelpunkt u besucht vor dem Scheitelpunkt v in einer durch die Ordnung der Angrenzen-Listen veranlassten Tiefensuche?
• Freie Grammatik-Mitgliedschaft des Zusammenhangs - Gegeben eine Grammatik ohne Zusammenhänge und eine Schnur, die kann spannen, durch diese Grammatik erzeugt werden?
• Horn-Satisfiability: In Anbetracht einer Reihe von Klauseln von Horn, ist dort eine variable Anweisung die befriedigt sie? Das ist die Version von P des boolean satisfiability Problem.
• Spiel des Lebens - Gegeben eine anfängliche Konfiguration des Spiels von Conway des Lebens, einer besonderen Zelle, und eine Zeit T (im unären), ist diese Zelle danach T Schritte lebendig?
• LZW (Algorithmus) (1978-Paradigma) Datenkompression - gegeben Schnuren s und t, wird, s mit einer LZ78 Methode zusammenpressend, tragen t zum Wörterbuch bei? (Bemerken Sie, dass für die LZ77 Kompression wie gzip das viel leichter ist, als das Problem zu abnimmt, "Ist t in s?".)
• Die Typ-Schlussfolgerung für teilweise Typen - Gegeben ein ungetippter Begriff von der Lambda-Rechnung, bestimmen Sie, ob dieser Begriff einen teilweisen Typ hat.

Um zu beweisen, dass ein gegebenes Problem in P P-complete ist, versucht man normalerweise, ein bekanntes P-complete Problem auf das gegebene zu reduzieren.

1999 haben Jin-Yi Cai und D. Sivakumar, auf Arbeit von Ogihara bauend, dass gezeigt, wenn dort eine spärliche Sprache besteht, die P-complete, dann L = P ist.

Probleme, die nicht bekannt sind, P-complete zu sein

Wie man

bekannt, sind einige Probleme nicht entweder NP-hard oder in P. Wie man verdächtigt, sind diese Probleme (z.B Factoring) schwierig. Ähnlich gibt es Probleme, die, wie man bekannt, entweder P-complete oder NC nicht sind, aber gedacht werden, zu parallelize schwierig zu sein. Beispiele schließen die Entscheidungsproblem-Formen ein, den größten allgemeinen Teiler von zwei Zahlen zu finden und zu bestimmen, was antwortet, dass der verlängerte Euklidische Algorithmus, wenn gegeben, zwei Zahlen zurückgeben würde.

Zeichen

• Greenlaw, Raymond, James Hoover und Walter Ruzzo. 1995. Grenzen, um Berechnung Anzupassen; P-Vollständigkeitstheorie. Internationale Standardbuchnummer 0-19-508591-4. - Entwickelt die Theorie, dann Kataloge 96 P-Complete Probleme.
• Satoru Miyano, Shuji Shiraishi und Takayoshi Shoudai. Eine Liste von P-Complete Problemen. Kyushu Universität, RIFIS TR CS 17. Dezember 1990.