Komplexitätsklasse - Complexity class

In der Berechnungskomplexitätstheorie ist eine Komplexitätsklasse ein Satz von Berechnungsproblemen mit verwandter ressourcenbasierter Komplexität . Die beiden am häufigsten analysierten Ressourcen sind Zeit und Speicher .

Im Allgemeinen wird eine Komplexitätsklasse in Bezug auf eine Art von Rechenproblem, ein Rechenmodell und eine begrenzte Ressource wie Zeit oder Speicher definiert . Insbesondere bestehen die meisten Komplexitätsklassen aus Entscheidungsproblemen , die mit einer Turingmaschine lösbar sind und sich durch ihren Zeit- oder Platzbedarf (Speicher) unterscheiden. Zum Beispiel ist die Klasse P die Menge von Entscheidungsproblemen, die durch eine deterministische Turingmaschine in polynomieller Zeit lösbar sind . Es gibt jedoch viele Komplexitätsklassen, die in Bezug auf andere Arten von Problemen (zB Zählprobleme und Funktionsprobleme ) definiert sind und andere Berechnungsmodelle verwenden (zB probabilistische Turing-Maschinen , interaktive Beweissysteme , Boolesche Schaltungen und Quantencomputer ).

Die Untersuchung der Beziehungen zwischen Komplexitätsklassen ist ein wichtiges Forschungsgebiet der theoretischen Informatik. Es gibt oft allgemeine Hierarchien von Komplexitätsklassen; beispielsweise ist es bekannt , dass eine Reihe von grundlegenden Zeit und Raum Komplexitätsklassen miteinander in der folgenden Weise beziehen: NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ Expspace (wobei ⊆ bezeichnet die Subset - Beziehung). Viele Zusammenhänge sind jedoch noch nicht bekannt; Beispielsweise betrifft eines der bekanntesten offenen Probleme in der Informatik, ob P gleich NP ist . Die Beziehungen zwischen den Klassen beantworten häufig Fragen zur grundlegenden Natur der Berechnung. Das P- gegen- NP- Problem beispielsweise hängt direkt mit der Frage zusammen, ob Nichtdeterminismus Computern Rechenleistung hinzufügt und ob Probleme mit einer Lösung, die schnell auf Korrektheit überprüft werden kann, auch schnell gelöst werden können.

Hintergrund

Komplexitätsklassen sind Sätze verwandter Rechenprobleme . Sie werden im Hinblick auf die Rechenschwierigkeiten bei der Lösung der in ihnen enthaltenen Probleme in Bezug auf bestimmte Rechenressourcen wie Zeit oder Speicher definiert. Formaler gesagt besteht die Definition einer Komplexitätsklasse aus drei Dingen: einer Art von Rechenproblem, einem Rechenmodell und einer begrenzten Rechenressource. Insbesondere bestehen die meisten Komplexitätsklassen aus Entscheidungsproblemen , die von einer Turingmaschine mit begrenzten Zeit- oder Raumressourcen gelöst werden können. Beispielsweise ist die Komplexitätsklasse P definiert als die Menge von Entscheidungsproblemen , die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können .

Rechenprobleme

Intuitiv ist ein Rechenproblem nur eine Frage, die ein Computer beantworten kann. Zum Beispiel "ist die natürliche Zahl n eine Primzahl ?" ist ein Problem, das ein Computer lösen könnte. Ein Rechenproblem wird mathematisch als die Menge von Antworten auf das Problem dargestellt. Im Primalitätsbeispiel wird das Problem (nennen Sie es PRIME ) durch die Menge aller natürlichen Primzahlen dargestellt: . In der Berechnungstheorie werden diese Antworten als Strings dargestellt ; zum Beispiel könnten im Primalitätsbeispiel die natürlichen Zahlen als Bitfolgen dargestellt werden , die Binärzahlen darstellen . Aus diesem Grund werden Rechenprobleme oft synonym als Sprachen bezeichnet ; zum Beispiel zu sagen, dass das PRIME- Problem in der Komplexitätsklasse NP liegt, ist äquivalent zu der Aussage, dass die Sprache PRIME in NP liegt . ${\displaystyle {\mathit {PRIME}}=\{n\in\mathbb{N} |n{\text{ ist eine Primzahl}}\}}$

Entscheidungsprobleme

Die am häufigsten analysierten Probleme in der theoretischen Informatik sind Entscheidungsprobleme – die Arten von Problemen, die als Ja-Nein-Fragen gestellt werden können . Das obige Primalitätsbeispiel ist beispielsweise ein Beispiel für ein Entscheidungsproblem, wie es durch die Ja-Nein-Frage "ist die natürliche Zahl n prim " dargestellt werden kann. In der Berechnungstheorie wird ein Entscheidungsproblem als die Menge von Eingabezeichenfolgen dargestellt, auf die ein Computer, der einen korrekten Algorithmus ausführt, mit "Ja" antworten würde. Im Primalitätsbeispiel ist PRIME der Satz von Strings, die natürliche Zahlen darstellen, die bei Eingabe in einen Computer, auf dem ein Algorithmus läuft, der korrekt auf Primalität testet , antwortet "ja, diese Zahl ist eine Primzahl". Dieses "Ja-Nein"-Format wird oft gleichbedeutend mit "Akzeptieren-Ablehnen" angegeben; das heißt, ein Algorithmus "akzeptiert" eine Eingabezeichenfolge, wenn die Antwort auf das Entscheidungsproblem "ja" ist, und "lehnt" ab, wenn die Antwort "nein" ist.

Obwohl einige Probleme nicht ohne weiteres als Entscheidungsprobleme ausgedrückt werden können, umfassen sie dennoch ein breites Spektrum an Rechenproblemen. Andere Arten von Problemen, durch die bestimmte Komplexitätsklassen definiert werden, sind Funktionsprobleme (zB FP ), Zählprobleme (zB #P ), Optimierungsprobleme und Promise-Probleme (siehe Abschnitt "Andere Arten von Problemen").

Computermodelle

Um den Begriff „Computer“ zu konkretisieren, werden in der theoretischen Informatik Probleme im Kontext eines Rechenmodells analysiert . Dies ist auch direkt relevant, um genaue Vorstellungen von Rechenressourcen wie "Zeit" und "Speicher" zu machen. In der Berechnungskomplexitätstheorie befassen sich Komplexitätsklassen mit den inhärenten Ressourcenanforderungen von Problemen und nicht mit den Ressourcenanforderungen, die davon abhängen, wie ein physischer Computer konstruiert ist. In der realen Welt können beispielsweise verschiedene Computer aufgrund ihrer Konstruktionsweise unterschiedliche Zeit- und Speicherkapazitäten benötigen, um dasselbe Problem zu lösen. Durch die Bereitstellung einer abstrakten mathematischen Darstellung von Computern abstrahieren Rechenmodelle überflüssige Komplexitäten der realen Welt (wie Unterschiede in der Prozessorgeschwindigkeit ), die das Verständnis grundlegender Prinzipien behindern.

Das am häufigsten verwendete Rechenmodell ist die Turing-Maschine . Während es andere Modelle gibt und viele Komplexitätsklassen in Bezug auf diese definiert werden (siehe Abschnitt "Andere Berechnungsmodelle" ), wird die Turing-Maschine verwendet, um die meisten grundlegenden Komplexitätsklassen zu definieren. Bei der Turing-Maschine wird der Begriff der Zeit anstelle von Standardzeiteinheiten wie der zweiten (die es unmöglich machen, die Laufzeit von der Geschwindigkeit physikalischer Hardware zu trennen) und Standardeinheiten des Speichers wie Bytes zu verwenden , abstrahiert als die Anzahl der elementaren Schritte, die eine Turing-Maschine unternimmt, um ein Problem zu lösen, und der Begriff des Speichers wird als die Anzahl der Zellen abstrahiert, die auf dem Band der Maschine verwendet werden. Diese werden im Folgenden näher erläutert.

Es ist auch möglich, die Blum-Axiome zu verwenden, um Komplexitätsklassen zu definieren, ohne sich auf ein konkretes Rechenmodell zu beziehen , aber dieser Ansatz wird in der Komplexitätstheorie weniger häufig verwendet.

Deterministische Turing-Maschinen

Eine Turingmaschine ist ein mathematisches Modell einer allgemeinen Rechenmaschine. Es ist das am häufigsten verwendete Modell in der Komplexitätstheorie, was zum großen Teil darauf zurückzuführen ist, dass es genauso leistungsfähig ist wie jedes andere Berechnungsmodell und mathematisch leicht zu analysieren ist. Wichtig ist, dass, wenn es einen Algorithmus gibt, der ein bestimmtes Problem löst, es auch eine Turing-Maschine gibt, die dasselbe Problem löst (dies ist als Church-Turing-These bekannt ); Dies bedeutet, dass angenommen wird, dass jeder Algorithmus als Turingmaschine dargestellt werden kann.

Mechanisch manipuliert eine Turing-Maschine (TM) Symbole (im Allgemeinen beschränkt auf die Bits 0 und 1, um eine intuitive Verbindung zu realen Computern herzustellen), die auf einem unendlich langen Bandstreifen enthalten sind. Das TM kann mit einem Tonbandkopf nacheinander lesen und schreiben. Die Operation wird vollständig durch einen endlichen Satz elementarer Anweisungen bestimmt, wie z 0, schreibe eine 1 und wechsel in den Zustand 6". Die Turing-Maschine beginnt nur mit der Eingabezeichenfolge auf ihrem Band und leert sich überall sonst. Das TM akzeptiert die Eingabe, wenn es in einen festgelegten Annahmezustand eintritt, und weist die Eingabe zurück, wenn es in einen Zurückweisungszustand eintritt. Die deterministische Turingmaschine (DTM) ist die grundlegendste Art der Turingmaschine. Es verwendet ein festes Regelwerk, um seine zukünftigen Handlungen zu bestimmen (weshalb es „ deterministisch “ genannt wird).

Ein Rechenproblem kann dann in Bezug auf eine Turing-Maschine als die Menge von Eingabestrings definiert werden, die eine bestimmte Turing-Maschine akzeptiert. Zum Beispiel ist das Primalitätsproblem PRIME von oben die Menge von Strings (die natürliche Zahlen darstellen), die eine Turing-Maschine, die einen Algorithmus ausführt , der korrekt auf Primalität testet, akzeptiert. Eine Turing-Maschine erkennt eine Sprache (denken Sie daran, dass "Problem" und "Sprache" in der Berechenbarkeits- und Komplexitätstheorie weitgehend synonym sind), wenn sie alle Eingaben akzeptiert, die in der Sprache enthalten sind, und eine Sprache entscheiden soll, wenn sie zusätzlich alle ablehnt Eingaben, die nicht in der Sprache sind (bestimmte Eingaben können dazu führen, dass eine Turing-Maschine ewig läuft, so dass die Entscheidbarkeit die Erkennbarkeit zusätzlich einschränkt , dass die Turing-Maschine bei allen Eingaben anhalten muss). Eine Turingmaschine, die ein Problem "löst", bedeutet im Allgemeinen eine, die die Sprache bestimmt.

Turingmaschinen ermöglichen intuitive Vorstellungen von „Zeit“ und „Raum“. Die Zeitkomplexität einer TM an einer bestimmten Eingabe ist die Anzahl der elementaren Schritte, die die Turing-Maschine durchführt, um entweder einen Annahme- oder Ablehnungszustand zu erreichen. Die Raumkomplexität ist die Anzahl von Zellen auf seinem Band, die es verwendet, um entweder einen Annahme- oder Zurückweisungszustand zu erreichen.

Nichtdeterministische Turingmaschinen

Eine Variante der deterministischen Turingmaschine (DTM) ist die nichtdeterministische Turingmaschine (NTM). Intuitiv ist ein NTM nur eine normale Turing-Maschine, die die zusätzliche Fähigkeit hat, mehrere mögliche zukünftige Aktionen von einem bestimmten Zustand aus zu untersuchen und einen Zweig zu "wählen", der akzeptiert (wenn überhaupt akzeptiert). Das heißt, während ein DTM nur einem Berechnungszweig folgen muss, kann man sich einen NTM als Berechnungsbaum vorstellen, der bei jedem Schritt in viele mögliche Berechnungspfade verzweigt (siehe Bild). Wenn mindestens ein Zweig des Baums mit einer "Akzeptieren"-Bedingung anhält, akzeptiert der NTM die Eingabe. Auf diese Weise kann man sich einen NTM so vorstellen, dass er gleichzeitig alle Berechnungsmöglichkeiten parallel untersucht und einen akzeptierenden Zweig auswählt. NTMs sollen keine physikalisch realisierbaren Modelle sein, sie sind einfach theoretisch interessante abstrakte Maschinen, die eine Reihe interessanter Komplexitätsklassen hervorbringen (die oft physikalisch realisierbare äquivalente Definitionen haben).

Die Zeitkomplexität eines NTM ist die maximale Anzahl von Schritten, die der NTM für jeden Zweig seiner Berechnung verwendet. In ähnlicher Weise ist die Raumkomplexität eines NTM die maximale Anzahl von Zellen, die der NTM in jedem Zweig seiner Berechnung verwendet.

DTMs können als Sonderfall von NTMs angesehen werden, die die Macht des Nichtdeterminismus nicht nutzen. Somit kann jede Berechnung, die von einem DTM durchgeführt werden kann, auch von einem äquivalenten NTM durchgeführt werden. Es ist auch möglich, beliebige NTMs mit einem DTM zu simulieren. Daher sind beide in Bezug auf die Berechenbarkeit gleichwertig. Die Simulation eines NTM mit einem DTM erfordert jedoch oft mehr Zeit und/oder Speicherressourcen; Wie sich zeigen wird, ist die Bedeutung dieser Verlangsamung für bestimmte Klassen von Rechenproblemen eine wichtige Frage in der Rechenkomplexitätstheorie.

Ressourcengrenzen

Komplexitätsklassen gruppieren Rechenprobleme nach ihren Ressourcenanforderungen. Dazu werden Rechenprobleme durch Obergrenzen für die maximale Menge an Ressourcen unterschieden, die der effizienteste Algorithmus benötigt, um sie zu lösen. Insbesondere befassen sich Komplexitätsklassen mit der Wachstumsrate der Ressourcenanforderungen, um ein Rechenproblem zu lösen, wenn die Eingabegröße zunimmt. Zum Beispiel wächst die Zeit, die zum Lösen von Problemen in der Komplexitätsklasse P benötigt wird, mit zunehmender Eingabegröße relativ langsam, während sie für Probleme der Komplexitätsklasse EXPTIME (oder genauer gesagt für Probleme in EXPTIME , die außerhalb liegen) vergleichsweise schnell wächst von P , seit ). Dieser Prozess wird unter Verwendung der großen O-Notation formalisiert . ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {EXPTIME}}}$

Beachten Sie, dass das Studium von Komplexitätsklassen in erster Linie dazu gedacht ist, die inhärente Komplexität zu verstehen, die zum Lösen von Rechenproblemen erforderlich ist. Komplexitätstheoretiker sind daher im Allgemeinen damit beschäftigt, die kleinste Komplexitätsklasse zu finden, in die ein Problem fällt, und sind daher damit beschäftigt, unter Verwendung des effizientesten Algorithmus zu identifizieren, in welche Klasse ein Rechenproblem fällt . Es kann beispielsweise einen Algorithmus geben, der ein bestimmtes Problem in exponentieller Zeit löst, aber wenn der effizienteste Algorithmus zur Lösung dieses Problems in polynomieller Zeit läuft, dann lässt sich die diesem Problem innewohnende Zeitkomplexität besser als polynomiell beschreiben.

Zeitgrenzen

Die Zeitkomplexität eines Algorithmus in Bezug auf das Turing-Maschinen-Modell ist die Anzahl von Schritten, die eine Turing-Maschine benötigt, um einen Algorithmus mit einer gegebenen Eingabegröße auszuführen. Formal ist die Zeitkomplexität für einen mit einer Turingmaschine M implementierten Algorithmus definiert als die Funktion , wobei die maximale Anzahl von Schritten ist, die M bei jeder Eingabe der Länge n macht . Angenommen, die Eingaben für M sind Binärzahlen. Dann gibt es zum Beispiel vier Eingaben der Größe zwei: 00, 01, 10 und 11. Sagen wir, dass das Ausführen von M auf 00 zehn Schritte erfordert, auf 01 zwölf Schritte, auf 10 acht Schritte und auf 11 fünfzehn Schritte . Die Laufzeit ist das Maximum dieser vier Laufzeiten: . ${\displaystyle t_{M}:\mathbb{N}\to\mathbb{N}}$${\displaystyle t_{M}(n)}$${\displaystyle t_{M}(2)}$${\displaystyle t_{M}(2)=15}$

Komplexitätsklassen befassen sich jedoch weniger mit bestimmten Laufzeitwerten und mehr mit der allgemeinen Klasse von Funktionen, in die die Zeitkomplexitätsfunktion fällt. Ist zum Beispiel die Zeitkomplexität ein Polynom ? Eine logarithmische Funktion ? Eine Exponentialfunktion ? Oder eine andere Art von Funktion? Da genaue Zeitkomplexitätsfunktionen oft komplizierte Ausdrücke sind, werden sie mit der großen O-Notation vereinfacht . Dies führt zu den grundlegendsten Sätzen von Zeitkomplexitätsklassen: DTIME und NTIME . Sie sind wie folgt definiert:

• Die Zeitkomplexitätsklasse ist die Sammlung aller Probleme, die von einer zeitdeterministischen Turingmaschine entscheidbar sind .${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle O(t(n))}$
• Die Zeitkomplexitätsklasse ist die Sammlung aller Probleme, die von einer zeitlich nichtdeterministischen Turingmaschine entscheidbar sind .${\displaystyle {\mathsf {NTIME}}(t(n))}$${\displaystyle O(t(n))}$

Wenn beispielsweise ein Problem X durch einen zeitlich ablaufenden Algorithmus gelöst werden kann, dann ist es in seit . Beachten Sie, dass es unter der großen O-Notation auch der Fall ist, dass , , und so weiter. Das bedeutet, dass sich DTIME- Klassen im Allgemeinen nicht gegenseitig ausschließen, sondern eine Hierarchie bilden: . Diese hierarchische Natur tritt häufig bei Komplexitätsklassen auf. ${\displaystyle t(n)=8n^{3}+2n+4}$${\displaystyle {\mathsf {DTIME}}(n^{3})}$${\displaystyle t(n)=8n^{3}+2n+4=O(n^{3})}$${\displaystyle 8n^{3}+2n+4=O(n^{4})}$${\displaystyle 8n^{3}+2n+4=O(n^{5})}$${\displaystyle {\mathsf {DTIME}}(n^{3})\subseteq}$${\displaystyle {\mathsf {DTIME}}(n^{4})\subseteq}$${\displaystyle {\mathsf {DTIME}}(n^{5})\subseteq \cdots}$

Raumgrenzen

Die Raumkomplexität eines Algorithmus in Bezug auf das Turing-Maschinenmodell ist die Anzahl der Zellen auf dem Band der Turing-Maschine, die erforderlich sind, um einen Algorithmus mit einer gegebenen Eingabegröße auszuführen. Formal ist die Raumkomplexität eines mit einer Turingmaschine M implementierten Algorithmus definiert als die Funktion , wobei die maximale Anzahl von Zellen ist, die M bei jeder Eingabe der Länge n verwendet . ${\displaystyle s_{M}:\mathbb{N}\to\mathbb{N}}$${\displaystyle s_{M}(n)}$

Die grundlegendsten Klassen der Raumkomplexität sind wie folgt definiert:

• Die Raumkomplexitätsklasse ist die Sammlung aller Probleme, die von einer raumdeterministischen Turingmaschine entscheidbar sind .${\displaystyle {\mathsf {DSPACE}}(s(n))}$${\displaystyle O(s(n))}$
• Die Raumkomplexitätsklasse ist die Sammlung aller Probleme, die von einer nichtdeterministischen Turingmaschine im Raum entscheidbar sind .${\displaystyle {\mathsf {NSPACE}}(s(n))}$${\displaystyle O(s(n))}$

Grundlegende Komplexitätsklassen

ALL ist die Klasse aller Entscheidungsprobleme . Viele wichtige Komplexitätsklassen werden durch Begrenzung der Zeit oder des Raums definiert, die von einem Algorithmus verwendet werden. Einige wichtige auf diese Weise definierte Komplexitätsklassen werden im Folgenden erläutert.

Zeitkomplexitätsklassen

Daran erinnern , dass die Zeitkomplexität Klasse die Sammlung aller Probleme, die entscheidbar sind durch eine Zeit deterministischen Turingmaschine und ist die Sammlung aller Probleme , die entscheidbar durch einen sind Zeit nicht deterministische Turing - Maschine. Zeitkomplexitätsklassen werden oft formal anhand dieser beiden Klassen definiert. ${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle O(t(n))}$${\displaystyle {\mathsf {NTIME}}(t(n))}$${\displaystyle O(t(n))}$

P und NP

P ist die Klasse der Probleme, die von einer deterministischen Turingmaschine in polynomieller Zeit lösbar sind, und NP ist die Klasse der Probleme, die von einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösbar sind . Oder formaler,

${\displaystyle {\mathsf{P}}=\bigcup_{k\in\mathbb{N}}{\mathsf{DTIME}}(n^{k})}$

${\displaystyle {\mathsf{NP}}=\bigcup_{k\in\mathbb{N}}{\mathsf{NTIME}}(n^{k})}$

P wird oft als die Klasse von Problemen bezeichnet, die von einem deterministischen Computer "schnell" oder "effizient" gelöst werden können, da die Zeitkomplexität der Lösung eines Problems in P relativ langsam mit der Eingabegröße zunimmt.

Ein wichtiges Merkmal der Klasse NP ist, dass sie äquivalent als die Klasse von Problemen definiert werden kann, deren Lösungen durch eine deterministische Turingmaschine in polynomieller Zeit verifizierbar sind . Das heißt, eine Sprache in ist NP , wenn eine vorhanden ist deterministisch polynomialer Zeit Turing - Maschine, wie die Prüfer genannt, die einen String als Eingabe und ein Zertifikat - String , und akzeptiert , wenn in der Sprache und Spuck ist , wenn nicht in der Sprache ist . Intuitiv dient das Zertifikat als Nachweis dafür, dass die Eingabe in der Sprache erfolgt. Diese Äquivalenz unterstreicht nicht nur einen grundlegenden Zusammenhang zwischen Nichtdeterminismus und Lösungsüberprüfbarkeit, sondern bietet auch eine nützliche Methode zum Beweisen einer Sprache in NP – identifizieren Sie einfach ein geeignetes Zertifikat und zeigen Sie, dass es in polynomieller Zeit verifiziert werden kann. ${\displaystyle w}$ ${\displaystyle c}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$

Während es einen offensichtlichen Unterschied zwischen der Klasse der effizient lösbaren und der nur effizient überprüfbaren Probleme zu geben scheint, stehen P und NP tatsächlich im Zentrum eines der berühmtesten ungelösten Probleme der Informatik: der P-gegen-NP- Problem. Es ist zwar bekannt, dass P NP (intuitiv sind deterministische Turing-Maschinen nur eine Unterklasse nichtdeterministischer Turing-Maschinen, die ihren Nichtdeterminismus nicht nutzen; oder nach der Verifiziererdefinition ist P die Klasse von Problemen, deren polynomiale Zeitverifizierer nur empfangen müssen die leere Zeichenfolge als ihr Zertifikat), ist nicht bekannt, ob NP unbedingt größer als P ist . Wenn P = NP , dann folgt, dass der Nichtdeterminismus keine zusätzliche Rechenleistung gegenüber dem Determinismus in Bezug auf die Fähigkeit bietet , schnell eine Lösung für ein Problem zu finden; das heißt, die Fähigkeit, alle möglichen Zweige der Berechnung zu untersuchen, bietet höchstens eine polynomielle Beschleunigung gegenüber der Fähigkeit, nur einen einzigen Zweig untersuchen zu können. Darüber hinaus wäre es folgen , dass , wenn ein Beweis für eine Probleminstanz, die sich schnell auf Richtigkeit überprüft werden kann , besteht (das heißt, wenn das Problem in ist NP ), dann gibt es auch einen Algorithmus existiert , die schnell konstruieren , dass der Nachweis (das heißt, die Problem ist in P ). Die überwältigende Mehrheit der Informatiker glaubt jedoch, dass P NP und die meisten heute verwendeten kryptographischen Schemata auf der Annahme beruhen, dass P NP . ${\displaystyle\subseteq}$${\displaystyle \neq}$${\displaystyle \neq}$

EXPTIME und NEXPTIME

EXPTIME ist die Klasse von Entscheidungsproblemen, die von einer deterministischen Turingmaschine in exponentieller Zeit lösbar sind, und NEXPTIME ist die Klasse von Entscheidungsproblemen, die von einer nichtdeterministischen Turingmaschine in exponentieller Zeit lösbar sind. Oder formaler,

${\displaystyle {\mathsf {EXPTIME}}=\bigcup_{k\in\mathbb {N} }{\mathsf {DTIME}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPTIME}}=\bigcup_{k\in\mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

EXPTIME ist eine strikte Obermenge von P und NEXPTIME ist eine strikte Obermenge von NP . Es ist ferner der Fall, dass EXPTIME NEXPTIME . Es ist nicht bekannt, ob dies richtig ist, aber wenn P = NP ist, muss EXPTIME gleich NEXPTIME sein . ${\displaystyle\subseteq}$

Raumkomplexitätsklassen

Daran erinnern , dass der Raum Komplexitätsklasse der Sammlung aller Probleme, die entscheidbar sind durch einen Raum deterministische Turing - Maschine und ist die Sammlung aller Probleme , die entscheidbar durch einen sind Raum nondeterministic Turing - Maschine. Raumkomplexitätsklassen werden oft formal anhand dieser beiden Klassen definiert. ${\displaystyle {\mathsf {DSPACE}}(s(n))}$${\displaystyle O(s(n))}$${\displaystyle {\mathsf {NSPACE}}(s(n))}$${\displaystyle O(s(n))}$

L und NL

Obwohl es möglich ist, logarithmische Zeitkomplexitätsklassen zu definieren , sind dies extrem enge Klassen, da sublineare Zeiten es einer Turing-Maschine nicht einmal ermöglichen, die gesamte Eingabe zu lesen (weil ). Es gibt jedoch eine sinnvolle Anzahl von Problemen, die im logarithmischen Raum gelöst werden können. Die Definitionen dieser Klassen erfordern eine Zweiband-Turingmaschine, damit die Maschine den gesamten Input speichern kann (es kann gezeigt werden, dass die Zweiband -Turingmaschine hinsichtlich der Berechenbarkeit der Einband-Turingmaschine gleichwertig ist ). Beim Turing-Maschinenmodell mit zwei Bändern ist ein Band das Eingabeband, das schreibgeschützt ist. Das andere ist das Arbeitsband, das sowohl Lesen als auch Schreiben ermöglicht und das Band, auf dem die Turing-Maschine Berechnungen durchführt. Die Raumkomplexität der Turingmaschine wird als Anzahl der Zellen gemessen, die auf dem Arbeitsband verwendet werden. ${\displaystyle \log n<n}$

L ist dann definiert als die Klasse der Probleme, die im logarithmischen Raum auf einer deterministischen Turingmaschine lösbar sind, und NL ist die Klasse der Probleme, die im logarithmischen Raum auf einer nichtdeterministischen Turingmaschine lösbar sind. Oder formaler,

${\displaystyle {\mathsf {L}}={\mathsf {DSPACE}}(\log n)}$

${\displaystyle {\mathsf {NL}}={\mathsf {NSPACE}}(\log n)}$

Das ist bekannt . Es ist jedoch nicht bekannt, ob eine dieser Beziehungen richtig ist. ${\displaystyle {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {P}}}$

PSPACE und NPSPACE

Die Komplexitätsklassen PSPACE und NPSPACE sind die Raumanaloga zu P und NP . Das heißt, PSPACE ist die Klasse von Problemen, die im Polynomraum durch eine deterministische Turingmaschine lösbar sind, und NPSPACE ist die Klasse von Problemen, die im Polynomraum durch eine nichtdeterministische Turingmaschine lösbar ist. Formeller,

${\displaystyle {\mathsf{PSPACE}}=\bigcup_{k\in\mathbb{N}}{\mathsf{DSPACE}}(n^{k})}$

${\displaystyle {\mathsf{NPSPACE}}=\bigcup_{k\in\mathbb{N}}{\mathsf{NSPACE}}(n^{k})}$

Obwohl nicht bekannt ist, ob P = NP ist , hat Savitchs Theorem bekanntermaßen gezeigt, dass PSPACE = NPSPACE ist . Es ist auch bekannt, dass P PSPACE , was intuitiv aus der Tatsache folgt, dass eine Turingmaschine, die in polynomieller Zeit arbeitet, nur in polynomiell viele Zellen schreiben kann, da das Schreiben in eine Zelle auf dem Band einer Turingmaschine als eine Zeiteinheit definiert ist. Es wird vermutet, dass P strikt kleiner als PSPACE ist, dies wurde jedoch nicht bewiesen. ${\displaystyle\subseteq}$

EXPSPACE und NEXPSPACE

Die Komplexitätsklassen EXPSPACE und NEXPSPACE sind die Raumanaloga zu EXPTIME und NEXPTIME . Das heißt, EXPSPACE ist die Klasse von Problemen, die im Exponentialraum durch eine deterministische Turingmaschine lösbar sind, und NEXPSPACE ist die Klasse von Problemen, die im Exponentialraum durch eine nichtdeterministische Turingmaschine lösbar ist. Oder formaler,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup_{k\in\mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPSPACE}}=\bigcup_{k\in\mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

Der Satz von Savitch legt fest, dass EXPSPACE = NEXPSPACE . Diese Klasse ist extrem breit: Sie ist bekanntlich eine strikte Obermenge von PSPACE , NP und P , und es wird angenommen, dass sie eine strikte Obermenge von EXPTIME ist .

Eigenschaften von Komplexitätsklassen

Schließung

Komplexitätsklassen haben eine Vielzahl von Abschlusseigenschaften . Entscheidungsklassen können beispielsweise unter Negation , Disjunktion , Konjunktion oder sogar unter allen Booleschen Operationen abgeschlossen sein . Darüber hinaus können sie auch nach einer Vielzahl von Quantifizierungsschemata abgeschlossen werden. P ist zum Beispiel unter allen Booleschen Operationen abgeschlossen und unter Quantifizierung über Domänen mit polynomieller Größe (obwohl sie wahrscheinlich nicht über Domänen mit exponentieller Größe abgeschlossen sind). Abschlusseigenschaften können beim Trennen von Klassen hilfreich sein – ein möglicher Weg zur Trennung zweier Komplexitätsklassen besteht darin, eine Abschlusseigenschaft zu finden, die die eine besitzt und die andere nicht.

Jede Klasse X , die nicht unter Negation abgeschlossen ist, hat eine Komplementklasse co-X , die aus den Komplementen der in X enthaltenen Sprachen besteht . Auf ähnliche Weise kann man die boolesche Abgeschlossenheit einer Klasse definieren und so weiter; dies wird jedoch seltener gemacht.

Abschlusseigenschaften sind einer der Hauptgründe dafür, dass viele Komplexitätsklassen so definiert sind, wie sie sind. Nehmen wir zum Beispiel ein Problem, das in Zeit (dh in linearer Zeit) gelöst werden kann, und eines, das bestenfalls in Zeit gelöst werden kann . Diese beiden Probleme sind in P , jedoch wächst die Laufzeit des zweiten erheblich schneller als die Laufzeit des ersten, wenn die Eingabegröße zunimmt. Man könnte sich fragen, ob es besser wäre, die Klasse der "effizient lösbaren" Probleme mit einer kleineren Polynomschranke zu definieren, wie , anstatt mit allen Polynomen, die so große Diskrepanzen zulässt. Es stellt sich jedoch heraus, dass die Polynome die kleinste Klasse von Funktionen sind, die die linearen Funktionen enthalten, die unter Addition, Multiplikation und Komposition abgeschlossen sind. Dies bedeutet, dass die Polynome die kleinste Klasse sind, die die Zusammensetzung "effizienter Algorithmen" ermöglicht; Das heißt, ein Polynom-Algorithmus, der eine Polynom-Zeit nennt Unterprogramm noch ergibt sich ein Polynom-Algorithmus. Wenn jedoch die Schranke verwendet würde, könnte das Zusammensetzen einer konstanten Anzahl von "effizienten" Algorithmen zu einem neuen Algorithmus führen, der nicht "effizient" ist. (Man beachte, dass die Definition von P auch deshalb nützlich ist, weil empirisch fast alle praktisch nützlichen Probleme in P tatsächlich polynomiale Laufzeiten niedriger Ordnung haben und fast alle praktisch nützlichen Probleme außerhalb von P keine bekannten Algorithmen mit kleine exponentielle Laufzeiten, dh mit Laufzeiten nahe bei 1.) ${\displaystyle t(n)=n}$${\displaystyle t(n)=n^{1000}}$${\displaystyle n^{2}}$${\displaystyle n^{2}}$${\displaystyle O(c^{n})}$${\displaystyle c}$

Härte und Vollständigkeit

Viele Komplexitätsklassen werden mit dem Konzept einer Reduktion definiert . Eine Reduktion ist eine Transformation eines Problems in ein anderes Problem. Es erfasst die informelle Vorstellung, dass ein Problem mindestens so schwierig ist wie ein anderes Problem. Wenn zum Beispiel ein Problem mit einem Algorithmus für gelöst werden kann , ist es nicht schwieriger als , und wir sagen, dass reduziert sich auf . Es gibt viele verschiedene Arten von Reduktionen, basierend auf der Reduktionsmethode, wie Cook-Reduktionen , Karp-Reduktionen und Levin-Reduktionen , und der Komplexität der Reduktionen, wie Polynomialzeit-Reduktionen oder Log-Space-Reduktionen . ${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$ ${\displaystyle Y}$

Die am häufigsten verwendete Reduktion ist eine Polynomialzeitreduktion. Dies bedeutet, dass der Reduktionsprozess polynomiale Zeit benötigt. Zum Beispiel kann das Problem des Quadrierens einer ganzen Zahl auf das Problem der Multiplikation zweier ganzer Zahlen reduziert werden. Dies bedeutet, dass ein Algorithmus zum Multiplizieren von zwei ganzen Zahlen verwendet werden kann, um eine ganze Zahl zu quadrieren. Dies kann in der Tat dadurch erfolgen, dass beiden Eingängen des Multiplikationsalgorithmus dieselbe Eingabe gegeben wird. Wir sehen also, dass das Quadrieren nicht schwieriger ist als die Multiplikation, da das Quadrieren auf die Multiplikation reduziert werden kann.

Dies motiviert das Konzept, dass ein Problem für eine Komplexitätsklasse schwierig ist . Ein Problem ist für eine Klasse von Problemen C schwer, wenn jedes Problem in C auf reduziert werden kann . Somit ist kein Problem in C schwieriger als , da wir mit einem Algorithmus für jedes Problem in C lösen können . Natürlich hängt der Begriff der harten Probleme von der Art der verwendeten Reduktion ab. Für Komplexitätsklassen, die größer als P sind , werden gewöhnlich Polynomialzeitreduktionen verwendet. Insbesondere ist die Menge der Probleme, die für NP schwierig sind, die Menge der NP-schweren Probleme. ${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

Wenn ein Problem in C ist und für C schwer ist , dann heißt es für C vollständig . Dies bedeutet, dass dies das schwierigste Problem in C ist (da es viele Probleme geben kann, die gleich schwer sind, könnte man sagen, dass es so schwer ist wie die schwierigsten Probleme in C ). Somit enthält die Klasse der NP- vollständigen Probleme die schwierigsten Probleme in NP in dem Sinne, dass sie am wahrscheinlichsten nicht in P vorkommen. Da das Problem P  =  NP nicht gelöst ist, kann man ein bekanntes NP reduzieren - ein vollständiges Problem, ₂ , zu einem anderen Problem, ₁ , würde anzeigen, dass es keine bekannte polynomielle Lösung für Π _{1 gibt} . Dies liegt daran, dass eine polynomielle Lösung von Π ₁ eine polynomielle Lösung von Π _{2 ergeben würde} . Da alle NP- Probleme auf die Menge reduziert werden können, würde das Auffinden eines NP- vollständigen Problems, das in polynomieller Zeit lösbar ist, bedeuten, dass P  =  NP . ${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

Beziehungen zwischen Komplexitätsklassen

Satz von Savitch

Der Satz von Savitch stellt fest, dass PSPACE = NPSPACE und EXPSPACE = NEXPSPACE . Eine zentrale Frage der Komplexitätstheorie ist, ob der Nichtdeterminismus einem Rechenmodell signifikante Macht verleiht. Dies ist zentral für das offene P- gegen- NP- Problem im Kontext der Zeit. Das Theorem von Savitch zeigt, dass der Nichtdeterminismus für den Raum nicht wesentlich mehr Leistung hinzufügt, wobei "signifikant" den Unterschied zwischen polynomialen und superpolynomialen Ressourcenanforderungen (oder für EXPSPACE , den Unterschied zwischen exponentiell und superexponentiell) bedeutet. Zum Beispiel beweist der Satz von Savitch, dass kein Problem, das einen exponentiellen Raum für eine deterministische Turingmaschine erfordert, durch eine nichtdeterministische Turingmaschine mit polynomialem Raum gelöst werden kann.

Hierarchiesätze

Aus der Definition von DTIME folgt, dass in if enthalten ist , da if . Diese Definition gibt jedoch keinen Hinweis darauf, ob diese Einbeziehung streng ist. Für Zeit- und Raumanforderungen werden die Bedingungen, unter denen die Inklusion streng ist, durch die Zeit- bzw. Raumhierarchiesätze gegeben. Sie werden Hierarchietheoreme genannt, weil sie eine richtige Hierarchie der Klassen induzieren, die durch Beschränkung der jeweiligen Ressourcen definiert sind. Die Hierarchiesätze ermöglichen quantitative Aussagen darüber, wie viel zusätzlicher Zeit- oder Raumbedarf benötigt wird, um die Zahl der lösbaren Probleme zu erhöhen. ${\displaystyle {\mathsf {DTIME}}(n^{k_{1}})}$${\displaystyle {\mathsf {DTIME}}(n^{k_{2}})}$${\displaystyle k_{1}\leq k_{2}}$${\displaystyle O(n^{k_{1}})\subseteq O(n^{k_{2}})}$${\displaystyle k_{1}\leq k_{2}}$

Der Zeithierarchiesatz besagt, dass

${\displaystyle {\mathsf {DTIME}}{\big (}f(n){\big)}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log ^{2} (f(n)){\big)}}$.

Der Satz der Raumhierarchie besagt, dass

${\displaystyle {\mathsf {DSPACE}}{\big (}f(n){\big)}\subsetneq {\mathsf {DSPACE}}{\big (}f(n)\cdot \log(f(n )){\groß )}}$.

Die Zeit- und Raumhierarchiesätze bilden die Grundlage für die meisten Trennungsergebnisse von Komplexitätsklassen. Zum Beispiel stellt das Zeithierarchie-Theorem fest, dass P strikt in EXPTIME enthalten ist , und das Raumhierarchie-Theorem stellt fest, dass L strikt in PSPACE enthalten ist .

Andere Berechnungsmodelle

Während deterministische und nicht-deterministische Turing-Maschinen die am häufigsten verwendeten Berechnungsmodelle sind, werden viele Komplexitätsklassen in Bezug auf andere Berechnungsmodelle definiert. Bestimmtes,

• Eine Reihe von Klassen werden mit probabilistischen Turingmaschinen definiert , darunter die Klassen BPP , PP , RP und ZPP
• Eine Reihe von Klassen werden mit interaktiven Beweissystemen definiert , einschließlich der Klassen IP , MA und AM
• Eine Reihe von Klassen werden unter Verwendung von Booleschen Schaltungen definiert , einschließlich der Klassen P/poly und ihrer Unterklassen NC und AC
• Eine Reihe von Klassen werden mit Quanten-Turing-Maschinen definiert , darunter die Klassen BQP und QMA

Diese werden im Folgenden näher erläutert.

Randomisierte Berechnung

Eine Reihe wichtiger Komplexitätsklassen werden mit der probabilistischen Turing-Maschine definiert , einer Variante der Turing-Maschine , die zufällige Münzen werfen kann. Diese Klassen helfen, die Komplexität randomisierter Algorithmen besser zu beschreiben .

Eine probabilistische Turing-Maschine ähnelt einer deterministischen Turing-Maschine, außer dass sie einer einzelnen Übergangsfunktion (einem Satz von Regeln für das weitere Vorgehen bei jedem Schritt der Berechnung) folgt, sondern bei jedem Schritt probabilistisch zwischen mehreren Übergangsfunktionen auswählt. Die Standarddefinition einer probabilistischen Turingmaschine spezifiziert zwei Übergangsfunktionen, so dass die Auswahl der Übergangsfunktion bei jedem Schritt einem Münzwurf ähnelt. Die bei jedem Schritt der Berechnung eingeführte Zufälligkeit führt zu einem Fehlerpotential; das heißt, Strings, die die Turing-Maschine akzeptieren soll, können manchmal zurückgewiesen werden, und Strings, die die Turing-Maschine zurückweisen soll, können manchmal akzeptiert werden. Als Ergebnis werden die Komplexitätsklassen basierend auf der probabilistischen Turing-Maschine zum großen Teil um den zulässigen Fehlerbetrag definiert. Formal werden sie über eine Fehlerwahrscheinlichkeit definiert . Eine probabilistische Turingmaschine erkennt eine Sprache mit Fehlerwahrscheinlichkeit, wenn: ${\displaystyle \epsilon}$${\displaystyle M}$${\displaystyle L}$${\displaystyle \epsilon}$

1. ein String in impliziert, dass${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ akzeptiert }}w]\geq 1-\epsilon}$
2. eine Zeichenfolge, die nicht in ist, bedeutet, dass${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ lehnt }}w]\geq 1-\epsilon}$

Wichtige Komplexitätsklassen

Die grundlegenden randomisierten Zeitkomplexitätsklassen sind ZPP , RP , co-RP , BPP und PP .

Die strengste Klasse ist ZPP (zero-error probabilistic polynomial time), die Klasse von Problemen, die in polynomieller Zeit durch eine probabilistische Turingmaschine mit Fehlerwahrscheinlichkeit 0 lösbar sind. Intuitiv ist dies die strengste Klasse probabilistischer Probleme, da sie keinerlei Fehler erfordert .

Eine etwas lockerere Klasse ist RP (randomized polynomial time), die keinen Fehler für Zeichenfolgen, die nicht in der Sprache enthalten sind, beibehält, aber begrenzte Fehler für Zeichenfolgen in der Sprache zulässt. Formaler gesagt ist eine Sprache in RP, wenn es eine probabilistische Polynomialzeit-Turingmaschine M gibt, so dass, wenn eine Zeichenfolge nicht in der Sprache ist, M immer ablehnt und wenn eine Zeichenfolge in der Sprache ist, M mit einer Wahrscheinlichkeit von mindestens 1 . akzeptiert /2. Die Klasse co-RP ist ähnlich definiert, außer dass die Rollen vertauscht sind: Fehler ist für Zeichenfolgen in der Sprache nicht zulässig, aber für Zeichenfolgen, die nicht in der Sprache enthalten sind. Zusammengenommen umfassen die Klassen RP und co-RP alle Probleme, die von probabilistischen Turingmaschinen mit einseitigem Fehler gelöst werden können .

Eine weitere Lockerung der Fehleranforderungen, um zweiseitige Fehler zu berücksichtigen, ergibt die Klasse BPP (probabilistische polynomiale Zeit mit begrenztem Fehler), die Klasse von Problemen, die in polynomieller Zeit durch eine probabilistische Turingmaschine mit einer Fehlerwahrscheinlichkeit kleiner als 1/3 (für beide Strings) in der Sprache und nicht in der Sprache). BPP ist die praktisch relevanteste der probabilistischen Komplexitätsklassen – Probleme in BPP haben effiziente randomisierte Algorithmen , die schnell auf realen Computern ausgeführt werden können. BPP steht auch im Zentrum des wichtigen ungelösten Problems in der Informatik, ob P=BPP , was bedeuten würde, dass Zufälligkeit die Rechenleistung von Computern nicht erhöht, dh jede probabilistische Turing-Maschine könnte durch eine deterministische Turing-Maschine simuliert werden mit höchstens polynomiale Verlangsamung.

Die breiteste Klasse effizient lösbarer probabilistischer Probleme ist PP (probabilistic polynomial time), die Menge von Sprachen, die von einer probabilistischen Turingmaschine in polynomialer Zeit mit einer Fehlerwahrscheinlichkeit von weniger als 1/2 für alle Strings lösbar sind.

ZPP , RP und co-RP sind alle Teilmengen von BPP , die wiederum eine Teilmenge von PP ist . Der Grund dafür ist intuitiv: Die Klassen, die null Fehler und nur einen einseitigen Fehler erlauben, sind alle in der Klasse enthalten, die zweiseitige Fehler erlaubt, und PP lockert einfach die Fehlerwahrscheinlichkeit von BPP . ZPP bezieht sich auf RP und Co-RP wie folgt: . Das heißt, ZPP besteht genau aus den Problemen, die sowohl in RP als auch in Co-RP vorkommen . Intuitiv folgt dies aus der Tatsache, dass RP und co-RP nur einseitige Fehler zulassen: co-RP lässt keinen Fehler für Strings in der Sprache zu und RP lässt keinen Fehler für Strings zu, die nicht in der Sprache sind. Wenn also ein Problem sowohl in RP als auch in co-RP auftritt , dann darf es keinen Fehler für Strings sowohl in als auch nicht in der Sprache geben (dh überhaupt kein Fehler), was genau die Definition von ZPP ist . ${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

Wichtige randomisierte Raumkomplexitätsklassen umfassen BPL , RL und RLP .

Interaktive Proofsysteme

Mit interaktiven Beweissystemen werden eine Reihe von Komplexitätsklassen definiert . Interaktive Beweise verallgemeinern die Beweisdefinition der Komplexitätsklasse NP und geben Einblicke in Kryptographie , Approximationsalgorithmen und formale Verifikation .

Interaktive Beweissysteme sind abstrakte Maschinen , die Berechnungen als den Austausch von Nachrichten zwischen zwei Parteien modellieren: einem Prüfer und einem Verifizierer . Die Parteien interagieren durch den Austausch von Nachrichten, und eine Eingabezeichenfolge wird vom System akzeptiert, wenn der Prüfer die Eingabe aufgrund der Nachrichten, die er vom Prüfer erhalten hat, akzeptiert. Der Beweiser hat eine unbegrenzte Rechenleistung, während der Verifizierer eine begrenzte Rechenleistung hat (die Standarddefinition interaktiver Beweissysteme definiert den Verifizierer als polynomiell zeitbegrenzt). Der Beweiser ist jedoch nicht vertrauenswürdig (dies verhindert, dass alle Sprachen vom Beweissystem trivial erkannt werden, indem der rechnerisch unbeschränkte Beweiser auflösen lässt, ob ein String in einer Sprache ist, und dann ein vertrauenswürdiges "JA" oder "NEIN" an den Verifizierer sendet ). ${\displaystyle P}$${\displaystyle V}$${\displaystyle P}$

Wichtige Komplexitätsklassen

Die Klasse NP ist ein einfaches Beweissystem, in dem der Verifizierer darauf beschränkt ist, eine deterministische Polynomialzeit- Turingmaschine zu sein und das Verfahren auf eine Runde beschränkt ist (d Zertifikat – an den Prüfer). Anders ausgedrückt, in der Definition der Klasse NP (der Menge von Entscheidungsproblemen, für die die Probleminstanzen, wenn die Antwort "JA" ist, Beweise haben, die in polynomieller Zeit durch eine deterministische Turingmaschine verifizierbar sind) ein Beweissystem ist, in dem die Beweis wird von einem nicht erwähnten Beweiser konstruiert und die deterministische Turingmaschine ist der Verifizierer. Aus diesem Grund kann NP auch als dIP (deterministischer interaktiver Beweis) bezeichnet werden, obwohl es selten als solcher bezeichnet wird.

Es stellt sich heraus, dass NP die volle Leistungsfähigkeit interaktiver Beweissysteme mit deterministischen (Polynomialzeit-)Verifizierern einfängt, weil gezeigt werden kann, dass für jedes Beweissystem mit einem deterministischen Verifizierer niemals mehr als eine einzige Messaging-Runde zwischen den Prüfer und Prüfer. Interaktive Beweissysteme, die eine größere Rechenleistung über Standardkomplexitätsklassen bieten, erfordern daher probabilistische Verifizierer, was bedeutet, dass die Fragen des Verifizierers an den Beweiser mit probabilistischen Algorithmen berechnet werden . Wie im obigen Abschnitt über randomisierte Berechnungen angemerkt , führen probabilistische Algorithmen Fehler in das System ein, so dass Komplexitätsklassen basierend auf probabilistischen Beweissystemen hinsichtlich einer Fehlerwahrscheinlichkeit ε definiert werden .

Die allgemeinste Komplexitätsklasse, die sich aus dieser Charakterisierung ergibt, ist die Klasse IP (interactive polynomial time), die die Klasse aller Probleme ist, die durch ein interaktives Beweissystem lösbar sind , wobei V probabilistische Polynomialzeit ist und das Beweissystem zwei Eigenschaften erfüllt: für eine Sprache${\displaystyle (P,V)}$${\displaystyle L\in {\mathsf {IP}}}$

1. (Vollständigkeit) ein String w in L impliziert${\displaystyle \Pr[V{\text{ akzeptiert }}w{\text{ nach Interaktion mit }}P]\geq {\tfrac {2}{3}}}$
2. (Tonheit) eine Saite w nicht in L impliziert${\displaystyle \Pr[V{\text{ akzeptiert }}w{\text{ nach Interaktion mit }}P]\leq {\tfrac {1}{3}}}$

Ein wichtiges Merkmal von IP ist, dass es PSPACE entspricht . Mit anderen Worten, jedes Problem, das durch ein interaktives Beweissystem in polynomialer Zeit gelöst werden kann, kann auch durch eine deterministische Turingmaschine mit polynomialen Raumressourcen gelöst werden und umgekehrt.

Eine Modifikation des Protokolls für IP erzeugt eine weitere wichtige Komplexitätsklasse: AM (Arthur-Merlin-Protokoll). In der Definition von interaktiven Beweissystemen, die von IP verwendet werden , konnte der Prüfer die vom Verifizierer in seiner probabilistischen Berechnung verwendeten Coins nicht sehen – er konnte nur die Nachrichten sehen, die der Verifizierer mit diesen Coins produzierte. Aus diesem Grund werden die Coins auch Private Random Coins genannt . Das interaktive Beweissystem kann so eingeschränkt werden, dass die vom Verifizierer verwendeten Münzen öffentliche Zufallsmünzen sind ; das heißt, der Prüfer kann die Münzen sehen. Formal ist AM als die Klasse von Sprachen mit einem interaktiven Beweis definiert, bei der der Verifizierer eine zufällige Zeichenfolge an den Beweiser sendet, der Beweiser mit einer Nachricht antwortet und der Verifizierer entweder akzeptiert oder ablehnt, indem er eine deterministische Polynomialzeitfunktion auf die Nachricht vom Prüfer. AM kann zu AM [ k ] verallgemeinert werden , wobei k die Anzahl der ausgetauschten Nachrichten ist (also in der verallgemeinerten Form das oben definierte Standard- AM AM [2]). Für alle gilt jedoch AM [ k ]= AM [2]. Das ist auch so . ${\displaystyle k\geq 2}$${\displaystyle {\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]}$

Andere Komplexitätsklassen, die unter Verwendung von interaktiven Beweissystemen definiert werden, umfassen MIP (Multiprover Interactive Polynomial Time) und QIP (Quantum Interactive Polynomial Time).

Boolesche Schaltungen

Ein alternatives Berechnungsmodell zur Turing-Maschine ist die Boolesche Schaltung , ein vereinfachtes Modell der digitalen Schaltungen, die in modernen Computern verwendet werden . Dieses Modell stellt nicht nur eine intuitive Verbindung zwischen der Berechnung in der Theorie und der Berechnung in der Praxis her, sondern ist auch ein natürliches Modell für ungleichmäßige Berechnungen (Berechnungen, bei denen unterschiedliche Eingabegrößen innerhalb desselben Problems unterschiedliche Algorithmen verwenden).

Formal ist eine Boolesche Schaltung ein gerichteter azyklischer Graph, in dem Kanten Drähte darstellen (die die Bitwerte 0 und 1 tragen), die Eingangsbits durch Quellknoten (Kanten ohne eingehende Kanten) dargestellt werden und alle Nicht-Quellknoten Logik darstellen Gatter (im Allgemeinen die UND- , ODER- und NICHT-Gatter ). Ein logisches Gatter wird als Ausgangsgatter bezeichnet und repräsentiert das Ende der Berechnung. Das Ein-/Ausgabeverhalten einer Schaltung mit Eingangsvariablen wird durch die Boolesche Funktion repräsentiert ; zum Beispiel wird bei Eingangsbits das Ausgangsbit der Schaltung mathematisch als dargestellt . Die Schaltung soll die Boolesche Funktion berechnen . ${\displaystyle C}$${\displaystyle C}$${\displaystyle n}$ ${\displaystyle f_{C}:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle x_{1},x_{2},...,x_{n}}$${\displaystyle b}$${\displaystyle b=f_{C}(x_{1},x_{2},...,x_{n})}$${\displaystyle C}$${\displaystyle f_{C}}$

Jede bestimmte Schaltung hat eine feste Anzahl von Eingangsknotenpunkten, sodass sie nur auf Eingänge dieser Größe wirken kann. Sprachen (die formalen Darstellungen von Entscheidungsproblemen ) enthalten jedoch Strings unterschiedlicher Länge, sodass Sprachen nicht vollständig von einer einzigen Schaltung erfasst werden können (dies steht im Gegensatz zum Turing-Maschinen-Modell, bei dem eine Sprache vollständig durch eine einzelne Turing-Maschine beschrieben wird, die kann auf jede Eingabegröße wirken). Eine Sprache wird also durch eine Schaltungsfamilie repräsentiert . Eine Schaltungsfamilie ist eine unendliche Liste von Schaltungen , wobei eine Schaltung mit Eingangsvariablen ist. Eine Schaltung Familie wird gesagt , eine Sprache zu entscheiden , wenn für jede Saite , in der Sprache ist , wenn und nur wenn , wo die Länge . Mit anderen Worten, eine Zeichenfolge der Größe ist in der Sprache der Schaltungsfamilie, wenn die Schaltung (die Schaltung mit der gleichen Anzahl von Eingangseckpunkten wie die Anzahl von Zeichen in ) als ihre Eingabe ausgewertet wird. ${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle C_{n}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle w}$${\displaystyle w}$${\displaystyle L}$${\displaystyle C_{n}(w)=1}$${\displaystyle n}$${\displaystyle w}$${\displaystyle w}$${\displaystyle n}$${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle C_{n}}$${\displaystyle w}$${\displaystyle w}$

Während mit Turing-Maschinen definierte Komplexitätsklassen in Bezug auf die Zeitkomplexität beschrieben werden , werden Schaltungskomplexitätsklassen in Bezug auf die Schaltungsgröße definiert – die Anzahl der Knoten in der Schaltung. Die Größenkomplexität einer Schaltungsfamilie ist die Funktion , wobei die Schaltungsgröße von ist . Daraus folgen natürlich die bekannten Funktionsklassen; Beispielsweise ist eine Schaltungsfamilie mit Polynomgröße eine solche, bei der die Funktion ein Polynom ist . ${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle f:\mathbb{N}\to\mathbb{N}}$${\displaystyle f(n)}$${\displaystyle C_{n}}$${\displaystyle f}$

Wichtige Komplexitätsklassen

Die Komplexitätsklasse P/poly ist die Menge von Sprachen, die durch Schaltungsfamilien polynomialer Größe entscheidbar sind. Es stellt sich heraus, dass zwischen Schaltungskomplexität und Zeitkomplexität ein natürlicher Zusammenhang besteht. Intuitiv hat eine Sprache mit geringer Zeitkomplexität (d. h. relativ wenige sequentielle Operationen auf einer Turing-Maschine) auch eine geringe Schaltungskomplexität (d. h. erfordert relativ wenige boolesche Operationen). Formal kann gezeigt werden, dass, wenn eine Sprache in ist , wo eine Funktion ist , sie Schaltungskomplexität hat . Daraus folgt unmittelbar, dass . Mit anderen Worten, jedes Problem, das in polynomieller Zeit durch eine deterministische Turingmaschine gelöst werden kann, kann auch durch eine Schaltungsfamilie mit polynomialer Größe gelöst werden. Außerdem ist die Inklusion richtig, dh (z. B. gibt es einige unentscheidbare Probleme , die in P/poly enthalten sind ). ${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle t}$${\displaystyle t:\mathbb{N}\to\mathbb{N}}$${\displaystyle O(t^{2}(n))}$${\displaystyle {\mathsf {\color {Blau}P}}\subset {\textsf {P/poly}}}$${\displaystyle {\textsf {P}}\subset {\textsf {P/poly}}}$

P/poly hat eine Reihe von Eigenschaften, die es für das Studium der Beziehungen zwischen Komplexitätsklassen sehr nützlich machen. Insbesondere ist es hilfreich bei der Untersuchung von Problemen im Zusammenhang mit P versus NP . Wenn es zum Beispiel eine Sprache in NP gibt, die nicht in P/poly ist , dann . P/poly ist auch hilfreich bei der Untersuchung von Eigenschaften der Polynomhierarchie . Wenn zum Beispiel NP ⊆ P / poly , dann PH kollabiert . Eine vollständige Beschreibung der Beziehungen zwischen P/poly und anderen Komplexitätsklassen finden Sie unter " Bedeutung von P/poly ". P/poly ist auch beim allgemeinen Studium der Eigenschaften von Turing-Maschinen hilfreich , da die Klasse äquivalent als die Klasse von Sprachen definiert werden kann, die von einer Polynomialzeit-Turingmaschine mit einer polynomisch beschränkten Beratungsfunktion erkannt werden . ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$${\displaystyle \Sigma_{2}^{\mathsf {P}}}$

Zwei Unterklassen von P/poly , die selbst interessante Eigenschaften haben, sind NC und AC . Diese Klassen werden nicht nur durch ihre Schaltungsgröße, sondern auch durch ihre Tiefe definiert . Die Tiefe einer Schaltung ist die Länge des längsten gerichteten Pfads von einem Eingangsknoten zum Ausgangsknoten. Die Klasse NC ist die Menge von Sprachen, die durch Schaltungsfamilien gelöst werden können, die nicht nur auf polynomielle Größe, sondern auch auf polylogarithmische Tiefe beschränkt sind. Die Klasse AC ist ähnlich wie NC definiert , jedoch dürfen Gatter unbegrenztes Auffächern haben (d. h. die UND- und ODER-Gatter können auf mehr als zwei Bits angewendet werden). NC ist eine bemerkenswerte Klasse, da sie äquivalent als die Klasse von Sprachen mit effizienten parallelen Algorithmen definiert werden kann .

Quantenberechnung

Die in der Quanteninformatik wichtigen Klassen BQP und QMA werden mit Hilfe von Quanten-Turing-Maschinen definiert .

Andere Arten von Problemen

Während die meisten Komplexitätsklassen Gruppen von Entscheidungsproblemen sind , gibt es auch eine Reihe von Komplexitätsklassen, die in Bezug auf andere Arten von Problemen definiert sind. Insbesondere gibt es Komplexitätsklassen bestehend aus Zählproblemen , Funktionsproblemen und Zusageproblemen . Diese werden im Folgenden näher erläutert.

Zählprobleme

Ein Zählproblem fragt nicht nur, ob eine Lösung existiert (wie bei einem Entscheidungsproblem ), sondern fragt, wie viele Lösungen existieren. Das Entscheidungsproblem CYCLE fragt beispielsweise, ob ein bestimmter Graph G einen einfachen Zyklus hat (die Antwort ist ein einfaches Ja/Nein); das zugehörige Zählproblem (ausgesprochen "scharfer Zyklus") fragt, wie viele einfache Zyklen G hat. Die Ausgabe für ein Zählproblem ist somit eine Zahl, im Gegensatz zur Ausgabe für ein Entscheidungsproblem, die ein einfaches Ja/Nein (oder Akzeptieren/Ablehnen, 0/1 oder ein anderes äquivalentes Schema) ist. Während also Entscheidungsprobleme mathematisch als dargestellt werden , formale Sprachen , Zählen Probleme mathematisch als dargestellte Funktionen : ein Zählproblem wird als Funktion formalisiert , so dass für einen Eingang , ist die Anzahl der Lösungen. Zum Beispiel in dem CYCLE Problem ist die Eingabe ein Graphen G (als Folge von dargestellten Bits ) und ist die Anzahl der Zyklen in einfachen G . ${\displaystyle {\mathit {\#CYCLE}}}$${\displaystyle f:\{0,1\}^{*}\to \mathbb{N}}$${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle f(w)}$${\displaystyle f(G)}$

Zählprobleme treten in einer Reihe von Bereichen auf, darunter statistische Schätzungen , statistische Physik , Netzwerkdesign und Wirtschaftswissenschaften .

Wichtige Komplexitätsklassen

#P (ausgesprochen "scharfes P") ist eine wichtige Klasse von Zählproblemen, die man sich als die Zählversion von NP vorstellen kann . Die Verbindung zu NP ergibt sich aus der Tatsache, dass die Anzahl der Lösungen eines Problems gleich der Anzahl der akzeptierenden Zweige im Berechnungsbaum einer nichtdeterministischen Turingmaschine ist. #P ist somit formal wie folgt definiert:

#P ist die Menge aller Funktionen , so dass es eine Polynomzeit nichtdeterministischen Turing Maschine M , so dass für alle , gleich die Anzahl der Verzweigungen in der Annahme M ‚s Berechnungsbaum auf w .${\displaystyle f:\{0,1\}^{*}\to \mathbb{N}}$${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle f(w)}$

Und so wie NP sowohl im Hinblick auf Nichtdeterminismus als auch im Sinne eines Verifizierers (dh als interaktives Beweissystem ) definiert werden kann, kann auch #P äquivalent im Sinne eines Verifizierers definiert werden. Daran erinnert , dass ein Entscheidungsproblem in ist NP , wenn es ein Polynom-Zeit überprüfbar existiert Zertifikat zu einem Problem instanz , die gegeben ist, NP fragt , ob es einen Nachweis der Mitgliedschaft besteht (ein Zertifikat) für die Eingabe , die für die Korrektheit in Polynom überprüft werden kann Zeit. Die Klasse #P fragt, wie viele solcher Zertifikate existieren. In diesem Zusammenhang wird #P wie folgt definiert:

#P ist die Menge von Funktionen, so dass es eine polynomielle und eine polynomiale Turingmaschine V (den Verifizierer) gibt, so dass für jedes , . Mit anderen Worten, gleich der Größe des Satzes, der alle Zertifikate mit Polynomgröße enthält.${\displaystyle f:\{0,1\}^{*}\to \mathbb{N}}$${\displaystyle p:\mathbb{N}\to\mathbb{N}}$${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle f(w)={\Big |}{\big\{}c\in\{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Groß |}}$${\displaystyle f(w)}$

Funktionsprobleme

Zählprobleme sind eine Teilmenge einer breiteren Klasse von Problemen, die als Funktionsprobleme bezeichnet werden . Ein Funktionsproblem ist ein Rechenproblem, bei dem für jede Eingabe eine einzelne Ausgabe (einer Gesamtfunktion ) erwartet wird, die Ausgabe jedoch komplexer ist als die eines Entscheidungsproblems . Bei Funktionsproblemen ist die Ausgabe nicht einfach 'ja' oder 'nein'. Die Komplexitätsklasse FP ist die Menge der Funktionsprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können .

Probleme mit Versprechen

Zusammenfassung der Beziehungen zwischen Komplexitätsklassen

Die folgende Tabelle zeigt einige der Klassen von Problemen, die in der Komplexitätstheorie betrachtet werden. Wenn Klasse X eine strikte Teilmenge von Y ist , dann wird X unter Y mit einer dunklen Linie angezeigt , die sie verbindet. Wenn X eine Teilmenge ist, aber nicht bekannt ist, ob es sich um gleiche Mengen handelt, ist die Linie heller und gepunktet. Technisch gesehen bezieht sich die Aufteilung in entscheidbare und unentscheidbare eher auf das Studium der Berechenbarkeitstheorie , ist aber nützlich, um die Komplexitätsklassen ins rechte Licht zu rücken .

		Entscheidungsproblem
Typ 0 (rekursiv aufzählbar)				Unentscheidbar
Entscheidbar
EXPSPACE
NÄCHSTES ZEIT
EXPTIME
PSPACE
Typ 1 (kontextsensitiv)
		co-NP	BQP		NP
			BPP
		P
	NC
Typ 2 (kontextfrei)
Typ 3 (Normal)

Siehe auch

• Liste der Komplexitätsklassen

Verweise

Literaturverzeichnis

• Arora, Sanjeev ; Barak, Boas (2009). Computational Complexity: Ein moderner Ansatz . Cambridge University Press. ISBN 978-0-521-42426-4.
• Sipser, Michael (2006). Einführung in die Rechentheorie (2. Aufl.). USA: Thomson-Kurstechnologie. ISBN 978-0-534-95097-2.

Weiterlesen

• The Complexity Zoo : Eine riesige Liste von Komplexitätsklassen, eine Referenz für Experten.
• Neil Immermann . "Computational Complexity Theory" . Archiviert vom Original am 16.04.2016. Enthält ein Diagramm, das die Hierarchie der Komplexitätsklassen und ihre Zusammengehörigkeit zeigt.
• Michael Garey und David S. Johnson : Computer und Widerspenstigkeit: Ein Leitfaden zur Theorie der NP-Vollständigkeit. New York: WH Freeman & Co., 1979. Die Standardreferenz zu NP-vollständigen Problemen - eine wichtige Kategorie von Problemen, deren Lösungen eine unpraktisch lange Berechnungszeit zu benötigen scheinen.