P (Komplexität)

Im Computerkomplexitätstheorie, P, auch bekannt als P -Zeit oder Time(nO (1)), ist eine grundlegende Komplexitätsklasse. Es enthält alles Entscheidungsprobleme das kann durch a gelöst werden deterministische Turing -Maschine Verwendung einer Polynom Menge von Berechnungszeit, oder Polynomzeit.

Cobhams These Es ist der Ansicht, dass P die Klasse von Rechenproblemen ist, die "effizient lösbar" oder "sindflehbar"Das ist ungenau: In der Praxis haben einige Probleme, die nicht in P sind Faustregel.

Definition

A Sprache L ist in p, wenn und nur wenn es eine deterministische Turing -Maschine gibt M, so dass

  • M Läuft für Polynomzeit für alle Eingänge
  • Für alle x in L, M Ausgänge 1
  • Für alle x nicht in L, M Ausgänge 0

P kann auch als einheitliche Familie von angesehen werden Boolesche Schaltungen. Eine Sprache L ist in p, wenn und nur wenn es vorhanden ist a Polynomzeituniform Familie der Booleschen Schaltungen , so dass

  • Für alle , nimmt n Bits als Eingang und Ausgabe 1 Bit
  • Für alle x in L,
  • Für alle x nicht in L,

Die Schaltungsdefinition kann geschwächt werden, um nur a zu verwenden Logspace -Uniform Familie, ohne die Komplexitätsklasse zu ändern.

Bemerkenswerte Probleme in p

Es ist bekannt, dass P viele natürliche Probleme enthält, einschließlich der Entscheidungsversionen von Lineares Programmieren, und finden a Maximale Matching. Im Jahr 2002 wurde gezeigt, dass das Problem der Bestimmung, ob eine Zahl ist Prime ist in P.[1] Die verwandte Klasse von Funktionsprobleme ist FP.

Für P sind mehrere natürliche Probleme abgeschlossen, einschließlich st-Konnektivität (oder Erreichbarkeit) auf alternierende Grafiken.[2] Der Artikel über P-Complete-Probleme Listet weitere relevante Probleme in P. auf

Beziehungen zu anderen Klassen

Eine Verallgemeinerung von p ist Np, was die Klasse von ist Entscheidungsprobleme entschlossen von a Nichtdeterministische Turing-Maschine Das läuft herein Polynomzeit. Äquivalent ist es die Klasse von Entscheidungsproblemen, bei der jede "Ja" -Instanz über ein Polynomgrößenzertifikat verfügt und Zertifikate durch eine polynomiale zeitdeterministische Turing -Maschine überprüft werden können. Die Klasse von Problemen, für die dies für die "Nein" -Abgleiche gilt, heißt Co-NP. P ist trivial eine Untergruppe von NP und Co-NP; Die meisten Experten glauben, dass es sich um eine ordnungsgemäße Untergruppe handelt.[3] Obwohl dieser Glaube (der Hypothese) bleibt unbewiesen. Ein weiteres offenes Problem ist, ob NP = Co-NP; da p = co-p,[4] Eine negative Antwort würde bedeuten .

P ist auch bekannt als mindestens so groß wie L, die Klasse von Problemen, die in a enttäuscht werden können logarithmisch Menge von Speicherraum. Ein Entschlossenheit Platz kann nicht mehr als nutzen als Zeit, weil dies die Gesamtzahl möglicher Konfigurationen ist; Daher ist L eine Untergruppe von P. Ein weiteres wichtiges Problem ist, ob L = P. wir wissen, dass P = Al, die im logarithmischen Speicher lösbare Probleme durch Wechsel Turing -Maschinen. Es ist auch bekannt, dass P nicht größer ist als PSPACE, die Klasse von Problemen, die im Polynomraum enttäuscht werden. Auch hier ist p = PSPACE ein offenes Problem. Zusammenfassen:

Hier, Nachfolger Ist die Klasse von Problemen in Exponentialzeit lösbar. Von allen oben gezeigten Klassen sind nur zwei strenge Hälfte bekannt:

  • P ist streng in der Expime enthalten. Infolgedessen liegen alle expime-harter Probleme außerhalb von P, und mindestens eine der Contantments rechts von P oben ist streng (tatsächlich wird allgemein angenommen, dass alle drei streng sind).
  • L ist streng in PSPACE enthalten.

Die schwierigsten Probleme in P sind P-Complete Probleme.

Eine weitere Verallgemeinerung von P ist P/polyoder ungleichmäßige Polynomzeit. Wenn ein Problem in P/Poly liegt, kann es in deterministischer Polynomzeit gelöst werden, vorausgesetzt, eine Beratungszeichenfolge wird angegeben, der nur von der Länge des Eingangs abhängt. Im Gegensatz zu NP muss die Polynomzeitmaschine jedoch keine betrügerischen Ratschläge erkennen. Es ist kein Verifizierer. P/Poly ist eine große Klasse, die fast alle praktischen Probleme enthält, einschließlich aller von BPP. Wenn es NP enthält, dann die Polynomhierarchie bricht auf die zweite Ebene zusammen. Andererseits enthält es auch einige unpraktische Probleme, einschließlich einiger unentscheidbare Probleme wie die unäre Version eines unentscheidbaren Problems.

1999 zeigten Jin-yi Cai und D. Sivakumar, die auf Arbeiten von Mitsunori Ogihara aufbauten spärliche Sprache Das ist P-Complete, dann l = P.[5]

Eigenschaften

Polynomzeitalgorithmen werden unter Zusammensetzung geschlossen. Intuitiv besagt dies, dass, wenn man eine Funktion schreibt, die annimmt, dass Funktionsaufrufe konstante Zeit sind, und wenn die genannten Funktionen selbst eine Polynomzeit erfordern, benötigt der gesamte Algorithmus die Polynomzeit. Eine Folge davon ist, dass P ist niedrig für sich selbst. Dies ist auch einer der Hauptgründe dafür, dass P als maschinenunabhängige Klasse angesehen wird. jede Maschine "Funktion" wie z. ZufallszugriffDies kann in der Polynomzeit simuliert werden, kann einfach mit dem Haupt-Polynom-Zeit-Algorithmus komponiert werden, um ihn auf einen Polynom-Zeitalgorithmus auf einer grundlegenden Maschine zu reduzieren.

Sprachen in P sind ebenfalls unter Umkehrung geschlossen, Überschneidung, Union, Verkettung, Kleene -Schließung, umgekehrt Homomorphismus, und Ergänzung.[6]

Reine Existenznachweise von Polynom-Zeit-Algorithmen

Einige Probleme sind in der Polynomzeit lösbar, aber für die Lösung ist kein Betonalgorithmus bekannt. Zum Beispiel die Robertson -Seymour -Theorem garantiert, dass es eine endliche Liste von gibt Verbotene Minderjährige Das charakterisiert (zum Beispiel) den Satz von Graphen, die in einen Torus eingebettet werden können; Darüber hinaus zeigten Robertson und Seymour, dass es ein O gibt ((n3) Algorithmus zur Bestimmung, ob ein Diagramm eine bestimmte Grafik als Moll hat. Dies ergibt a nicht konstruktiver Beweis Dass es einen Polynom-Zeit-Algorithmus gibt, um festzustellen, ob ein bestimmter Diagramm auf einen Torus eingebettet werden kann, obwohl für dieses Problem kein Betonalgorithmus bekannt ist.

Alternative Charakterisierungen

Im Beschreibende Komplexität, P kann als die Probleme beschrieben werden FO (LFP), das Logik erster Ordnung mit einer am wenigsten fester Punkt Der Bediener fügte ihm auf geordnete Strukturen hinzu. In Immerman 1999 Lehrbuch zur beschreibenden Komplexität,[7] Imerman schreibt dieses Ergebnis Vardi zu[8] und Immerman.[9]

Es wurde 2001 veröffentlicht, dass die P -Zeit (positiv) entspricht (positiv) Verbreitungsgrammatiken.[10]

Geschichte

Kozen[11] besagt, dass Cobham und Edmonds werden "allgemein der Erfindung des Begriffs der Polynomzeit zugeschrieben". Cobham erfand die Klasse als eine robuste Art der Charakterisierung effizienter Algorithmen und führte zu Cobhams These. Jedoch, H. C. Pocklington, in einem Papier von 1910,,[12][13] analysierte zwei Algorithmen zur Lösung quadratischer Kongruenzen und stellte fest, dass man sich Zeit brauchte, "proportional zu einer Kraft des Logarithmus des Moduls" zu Unterscheidung zwischen einem Algorithmus, der in der Polynomzeit lief, im Vergleich zu einem, der dies nicht tat.

Anmerkungen

  1. ^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "Primes ist in p",", Annalen der Mathematik 160 (2004), Nr. 2, S. 781–793.
  2. ^ Immerman, Neil (1999). Beschreibende Komplexität. New York: Springer-Verlag. ISBN 978-0-387-98600-5.
  3. ^ Johnsonbaugh, Richard; Schaefer, Marcus, Algorithmen, 2004 Pearson Education, Seite 458, ISBN0-02-360692-4
  4. ^ "Komplexitätstheorie - Warum ist Co -P = P". Paketüberfluss. Archiviert vom Original am 14. Oktober 2020. Abgerufen 2020-10-14.
  5. ^ Jin-yi Cai und D. Sivakumar. Spärliche harte Sätze für P: Auflösung einer Vermutung von Hartmanis. Journal of Computer and System Sciences, Band 58, Ausgabe 2, S. 280–296. 1999. ISSN 0022-0000. Bei Citeseer
  6. ^ Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Einführung in die Automatentheorie, Sprachen und Berechnung (2. ed.). Boston: Addison-Wesley. S. 425–426. ISBN 978-0201441246.
  7. ^ Immerman, Neil (1999). Beschreibende Komplexität. New York: Springer-Verlag. p. 66. ISBN 978-0-387-98600-5.
  8. ^ Vardi, Moshe Y. (1982). "Die Komplexität relationaler Abfragsprachen". STOC '82: Verfahren des vierzehnten jährlichen ACM -Symposiums über die Theorie des Computers. S. 137–146. doi:10.1145/800070.802186.
  9. ^ Imerman, Neil (1982). "Relationale Abfragen, die in Polynomzeit berechnet werden". STOC '82: Verfahren des vierzehnten jährlichen ACM -Symposiums über die Theorie des Computers. S. 147–152. doi:10.1145/800070.802187. Überarbeitete Version in Informationen und Kontrolle, 68 (1986), 86–104.
  10. ^ Laura Kallmeyer (2010). Analysen über kontextfreie Grammatiken übergehen. Springer Science & Business Media. S. 5 und 37. ISBN 978-3-642-14846-0. Zitieren http://mjn.host.cs.st-strows.ac.uk/publications/2001d.pdf für den Beweis
  11. ^ Kozen, Dexter C. (2006). Theorie der Berechnung. Springer. p. 4. ISBN 978-1-84628-297-3.
  12. ^ Pocklington, H. C. (1910–1912). "Die Bestimmung des Exponenten, zu dem eine Zahl gehört, die praktische Lösung bestimmter Kongruenzen und das Gesetz der quadratischen Gegenseitigkeit". Proc. Camb. Phil. SOC. 16: 1–5.
  13. ^ Gautschi, Walter (1994). Mathematik der Berechnung, 1943–1993: Ein halbes Jahrhundert der Computermathematik: Mathematik der Berechnung 50-jähriges Jubiläum, 9. bis 13. August 1993, Vancouver, British Columbia. Providence, RI: American Mathematical Society. S. 503–504. ISBN 978-0-8218-0291-5.

Verweise

Externe Links