Computerkomplexitätstheorie

Im Theoretische Informatik, Computerkomplexitätstheorie konzentriert sich auf die Klassifizierung Rechenprobleme nach ihrer Ressourcenverwendung und in Bezug auf diese Klassen miteinander. Ein Computerproblem ist eine von einem Computer gelöste Aufgabe. Ein Berechnungsproblem ist durch mechanische Anwendung mathematischer Schritte wie eins löslich Algorithmus.

Ein Problem wird als von Natur aus schwierig angesehen, wenn seine Lösung erhebliche Ressourcen erfordert, unabhängig vom verwendeten Algorithmus. Die Theorie formalisiert diese Intuition, indem sie mathematisch vorstellt Berechnungsmodelle diese Probleme zu untersuchen und ihre zu quantifizieren Rechenkomplexität, d.h. Andere Komplexitätsmaße werden ebenfalls verwendet, wie z. B. die Kommunikationsmenge (verwendet in Kommunikationskomplexität), die Anzahl der Anzahl von Tore in einer Schaltung (verwendet in Komplexität der Schaltung) und die Anzahl der Prozessoren (verwendet in Parallele Computing). Eine der Rollen der Rechenkomplexitätstheorie besteht darin, die praktischen Grenzen der Computer zu bestimmen, was Computer können und was nicht. Das P gegen NP -Problem, einer der sieben Millennium Prize Problems, ist dem Gebiet der rechnerischen Komplexität gewidmet.^[1]

Eng verwandte Felder in Theoretische Informatik sind Analyse von Algorithmen und Computerbarkeitstheorie. Eine zentrale Unterscheidung zwischen der Analyse der Algorithmen und der Rechenkomplexitätstheorie besteht darin, dass erstere der Analyse der Menge an Ressourcen widmet das gleiche Problem lösen. Genauer gesagt versucht die Theorie der Computerkomplexität, Probleme zu klassifizieren, die mit angemessen eingeschränkten Ressourcen gelöst werden können oder nicht. Das Auferlegen von Einschränkungen der verfügbaren Ressourcen unterscheidet wiederum die Rechenkomplexität von der Computerbarkeitstheorie: Die letztere Theorie fragt, welche Arten von Problemen im Prinzip algorithmisch gelöst werden können.

Rechenprobleme

Eine reisende Verkäufer -Tour durch 14 deutsche Städte.

Probleminstanzen

A Rechenproblem kann als unendliche Sammlung von angesehen werden Instanzen zusammen mit einem Satz (möglicherweise leer) von Lösungen Für jeden Fall. Die Eingabezeichenfolge für ein Computerproblem wird als Probleminstanz bezeichnet und sollte nicht mit dem Problem selbst verwechselt werden. In der Theorie der Computerkomplexität bezieht sich ein Problem auf die zu lösene abstrakte Frage. Im Gegensatz dazu ist eine Instanz dieses Problems eine eher konkrete Äußerung, die als Input für ein Entscheidungsproblem dienen kann. Betrachten Sie zum Beispiel das Problem von Primalitätstest. Die Instanz lautet eine Zahl (z. B. 15) und die Lösung lautet "Ja", wenn die Zahl an der Primzahl und "Nein" ist (in diesem Fall ist 15 nicht Prim und die Antwort "Nein"). Einen anderen Weg, die Beispiel ist eine besondere Eingabe für das Problem und die Lösung ist der Ausgang, der dem angegebenen Eingang entspricht.

Um den Unterschied zwischen einem Problem und einer Instanz weiter hervorzuheben, betrachten Sie die folgende Instanz der Entscheidungsversion des Problem mit reisenden Verkäufern: Gibt es eine Route von höchstens 2000 Kilometern durch alle 15 größten Städte Deutschlands? Die quantitative Antwort auf diese spezielle Probleminstanz ist für die Lösung anderer Instanzen des Problems von geringem Nutzen, beispielsweise nach einer Roundreise durch alle Standorte in Mailand deren Gesamtlänge ist höchstens 10 km. Aus diesem Grund befasst sich die Komplexitätstheorie mit Rechenproblemen und nicht bestimmten Probleminstanzen.

Probleminstanzen darstellen

Bei der Prüfung von Computerproblemen ist eine Probleminstanz a Saite über ein Alphabet. Normalerweise wird das Alphabet als das binäre Alphabet (d. H. Der Satz {0,1}) angesehen, und daher sind die Zeichenfolgen Bitstrings. Wie in einer realen Welt Computer, andere mathematische Objekte als Bitstrings müssen angemessen codiert werden. Zum Beispiel, Ganzzahlen kann in dargestellt werden in Binärnotation, und Grafiken kann direkt über ihre kodiert werden Adjazenzmatrizen, oder durch Codieren ihrer Adjazenzlisten in binär.

Obwohl einige Beweise für komplexitätstheoretische Theoreme regelmäßig eine konkrete Auswahl der Eingabecodierung annehmen, versucht man, die Diskussion abstrahiert zu halten, um unabhängig von der Wahl der Codierung zu sein. Dies kann erreicht werden, indem sichergestellt werden, dass verschiedene Darstellungen effizient ineinander transformiert werden können.

Entscheidungsprobleme als formelle Sprachen

A Entscheidungsproblem hat nur zwei mögliche Ausgänge, Jawohl oder nein (oder abwechselnd 1 oder 0) bei jeder Eingabe.

Entscheidungsprobleme sind eines der zentralen Studienobjekte in der Computerkomplexitätstheorie. Ein Entscheidungsproblem ist eine spezielle Art von Computerproblem, deren Antwort entweder ist Jawohl oder neinoder abwechselnd entweder 1 oder 0. Ein Entscheidungsproblem kann als als angesehen werden formelle Sprache, wo die Sprachmitglieder Fälle sind, deren Ausgabe Ja ist, und die Nichtmitglieder sind die Fälle, deren Ausgabe Nein ist. Das Ziel ist es, mit Hilfe eines zu entscheiden Algorithmus, ob eine bestimmte Eingabezeichenfolge ein Mitglied der formalen Sprache ist. Wenn der Algorithmus, der dieses Problem entscheidet, die Antwort zurückgibt JawohlDer Algorithmus soll die Eingangszeichenfolge akzeptieren, ansonsten soll er die Eingabe ablehnen.

Ein Beispiel für ein Entscheidungsproblem ist das folgende. Die Eingabe ist ein willkürlicher Graph. Das Problem besteht darin, zu entscheiden, ob die angegebene Grafik ist in Verbindung gebracht oder nicht. Die mit diesem Entscheidungsproblem verbundene formale Sprache ist dann die Menge aller verbundenen Grafiken - um eine genaue Definition dieser Sprache zu erhalten, muss man entscheiden, wie Grafiken als binäre Zeichenfolgen codiert werden.

Funktionsprobleme

A Funktionsproblem ist ein Computerproblem, bei dem eine einzelne Ausgabe (von a Gesamtfunktion) wird für jeden Eingang erwartet, aber der Ausgang ist komplexer als der von a Entscheidungsproblem- Das heißt, die Ausgabe ist nicht nur ja oder nein. Bemerkenswerte Beispiele sind die Problem mit reisenden Verkäufern und die Ganzzahlfaktorisierungsproblem.

Es ist verlockend zu glauben, dass der Begriff von Funktionsproblemen viel reicher ist als der Begriff der Entscheidungsprobleme. Dies ist jedoch nicht wirklich der Fall, da Funktionsprobleme als Entscheidungsprobleme neu gestaltet werden können. Zum Beispiel kann die Multiplikation von zwei Ganzzahlen als Dreifachsatz ausgedrückt werden (aAnwesendbAnwesendc) so dass die Beziehung a×b=c hält. Die Entscheidung, ob ein bestimmtes Triple ein Mitglied dieses Satzes ist, entspricht der Lösung des Problems, zwei Zahlen zu multiplizieren.

Messung der Größe einer Instanz

Um die Schwierigkeit zu messen, ein Rechenproblem zu lösen, möchte man sehen, wie viel Zeit der beste Algorithmus benötigt, um das Problem zu lösen. Die Laufzeit kann jedoch im Allgemeinen von der Instanz abhängen. Insbesondere für größere Fälle benötigen größere Fälle mehr Zeit, um zu lösen. Die Zeit, die erforderlich ist, um ein Problem (oder den erforderlichen Raum oder ein Maß für die Komplexität) zu lösen, wird als Funktion der Größe der Instanz berechnet. Dies wird normalerweise als die Größe des Eingangs in Bits angesehen. Die Komplexitätstheorie ist daran interessiert, wie Algorithmen mit einer Zunahme der Eingangsgröße skalieren. Zum Beispiel, im Problem, zu finden, ob ein Diagramm verbunden ist, dauert es, wie viel mehr Zeit benötigt, um ein Problem für ein Diagramm mit 2n Scheitelpunkte im Vergleich zu der Zeit, die für eine Grafik mitgenommen wurde mit n Scheitelpunkte?

Wenn die Eingangsgröße ist nDie Zeit kann als Funktion von ausgedrückt werden n. Da die Zeit, die für verschiedene Eingaben derselben Größe benötigt wird, unterschiedlich sein kann, die schlimmste Zeitkomplexität t (n) ist definiert als die maximale Zeit, die alle Eingänge der Größe übernommen haben n. Wenn t (n) ist ein Polynom in ndann soll der Algorithmus a sein Polynomzeit Algorithmus. Cobhams These argumentiert, dass ein Problem mit einer praktikablen Menge an Ressourcen gelöst werden kann, wenn es einen Polynom-Zeit-Algorithmus zulässt.

Maschinenmodelle und Komplexitätsmaße

Turing Maschine

Eine Illustration einer Turing -Maschine

Eine Turing -Maschine ist ein mathematisches Modell einer allgemeinen Computermaschine. Es ist ein theoretisches Gerät, das Symbole manipuliert, die auf einem Bandstreifen enthalten sind. Turing -Maschinen sind nicht als praktische Computertechnologie gedacht, sondern als allgemeines Modell einer Computermaschine - alles von einem fortschrittlichen Supercomputer zu einem Mathematiker mit Bleistift und Papier. Es wird angenommen, dass wenn ein Problem durch einen Algorithmus gelöst werden kann, es eine Turing -Maschine gibt, die das Problem löst. In der Tat ist dies die Aussage der These der Kirche und tätige These. Darüber hinaus ist bekannt, dass alles, was uns heute mit anderen Berechnungsmodellen berechnet werden kann, wie z. RAM -Maschine, Conways Leben des Lebens, Mobilfunk Automaten, Lambda -Kalkül oder jede Programmiersprache kann auf einer Turing -Maschine berechnet werden. Da Turing -Maschinen mathematisch leicht zu analysieren sind und als so leistungsfähig angesehen werden wie jedes andere Berechnungsmodell, ist die Turing -Maschine das am häufigsten verwendete Modell in der Komplexitätstheorie.

Viele Arten von Turing -Maschinen werden verwendet, um Komplexitätsklassen zu definieren, wie z. deterministische Turing -Maschinen, Probabilistische Turing -Maschinen, Nichtdeterministische Turing-Maschinen, Quanten -Turing -Maschinen, Symmetrische Turing -Maschinen und Wechsel Turing -Maschinen. Sie sind alle grundsätzlich gleich stark, aber wenn Ressourcen (z. B. Zeit oder Raum) begrenzt sind, sind einige davon möglicherweise mächtiger als andere.

Eine deterministische Turing -Maschine ist die grundlegendste Turing -Maschine, die einen festen Satz von Regeln verwendet, um ihre zukünftigen Aktionen zu bestimmen. Eine probabilistische Turing -Maschine ist eine deterministische Turing -Maschine mit einer zusätzlichen Versorgung mit zufälligen Bits. Die Fähigkeit, probabilistische Entscheidungen zu treffen, hilft Algorithmen häufig, Probleme effizienter zu lösen. Algorithmen, die zufällige Bits verwenden, werden aufgerufen Randomisierte Algorithmen. Eine nicht deterministische Turing-Maschine ist eine deterministische Turing-Maschine mit einem zusätzlichen Merkmal des Nichtdeterminismus, mit dem eine Turing-Maschine mehrere mögliche zukünftige Aktionen aus einem bestimmten Zustand haben kann. Eine Möglichkeit, den Nichtdeterminismus anzuzeigen, besteht darin, dass die Turing-Maschine bei jedem Schritt in viele mögliche Rechenwege verzweigt. Wenn sie das Problem in einem dieser Zweige löst, soll es das Problem gelöst haben. Dieses Modell ist eindeutig nicht als physikalisch realisierbares Modell gedacht, sondern nur eine theoretisch interessante abstrakte Maschine, die zu besonders interessanten Komplexitätsklassen führt. Beispiele siehe Nichtdeterministischer Algorithmus.

Andere Maschinenmodelle

Viele Maschinenmodelle unterscheiden sich vom Standard Multitape-Turing-Maschinen wurden zum Beispiel in der Literatur vorgeschlagen Zufallszugriffsmaschinen. Vielleicht überraschenderweise kann jedes dieser Modelle in einen anderen konvertiert werden, ohne zusätzliche Rechenleistung zu liefern. Der Zeit- und Gedächtnisverbrauch dieser alternativen Modelle kann variieren.^[2] All diese Modelle gemeinsam sind, dass die Maschinen arbeiten deterministisch.

Einige Rechenprobleme sind jedoch leichter analysiert, wenn ungewöhnlichere Ressourcen. Beispielsweise ist eine nicht deterministische Turing-Maschine ein Computermodell, das sich verzweigen kann, um viele verschiedene Möglichkeiten gleichzeitig zu überprüfen. Die nicht deterministische Turing-Maschine hat sehr wenig damit zu tun, wie wir Algorithmen physisch berechnen möchten, aber ihre Verzweigung erfasst genau viele der mathematischen Modelle, die wir analysieren möchten, so dass so Nichtdeterministische Zeit ist eine sehr wichtige Ressource bei der Analyse von Rechenproblemen.

Komplexitätsmaßnahmen

Für eine genaue Definition dessen, was es bedeutet, ein Problem mit einem bestimmten Zeit- und Speicherplatz zu lösen, ein Rechenmodell wie das deterministische Turing -Maschine wird genutzt. Das erforderliche Zeit durch eine deterministische Turing -Maschine M auf Eingabe x Ist die Gesamtzahl der Zustandsübergänge oder Schritte, die die Maschine vornimmt, bevor sie die Antwort ("Ja" oder "Nein" ausgibt). Eine Turing -Maschine M soll innerhalb der Zeit operieren f(n) Wenn die Zeit erforderlich ist durch M Bei jedem Längeneingang n ist höchstens f(n). Ein Entscheidungsproblem A kann rechtzeitig gelöst werden f(n) Wenn es eine Turing -Maschine gibt, die rechtzeitig arbeitet f(n) Das löst das Problem. Da die Komplexitätstheorie daran interessiert ist, Probleme aufgrund ihrer Schwierigkeit zu klassifizieren, definiert man Probleme, die auf einigen Kriterien beruhen. Zum Beispiel die Anzahl der Probleme, die innerhalb der Zeit lösbar sind f(n) auf einer deterministischen Turing -Maschine wird dann mit bezeichnet Time(f(n)).

Analoge Definitionen können für den Raumanforderungen vorgenommen werden. Obwohl Zeit und Raum die bekanntesten Komplexitätsressourcen sind Komplexitätsmaß kann als rechnerische Ressource angesehen werden. Komplexitätsmaßnahmen werden sehr allgemein durch die definiert Blum -Komplexitäts -Axiome. Andere Komplexitätsmaße, die in der Komplexitätstheorie verwendet werden Kommunikationskomplexität, Komplexität der Schaltung, und Entscheidungsbaumkomplexität.

Die Komplexität eines Algorithmus wird häufig verwendet Big O Notation.

Beste, schlimmste und durchschnittliche Fallkomplexität

Visualisierung der schnelle Sorte Algorithmus das hat Durchschnittliche Fallleistung ${\ displaystyle {\ mathcal {o}} (n \ log n)}$.

Das Bester, schlimmster und durchschnittlicher Fall Komplexität bezieht sich auf drei verschiedene Arten zur Messung der zeitlichen Komplexität (oder eines anderen Komplexitätsmaßes) verschiedener Eingaben derselben Größe. Da einige Eingaben der Größe n Möglicherweise definieren wir schneller als andere, wir definieren die folgenden Komplexitäten:

1. Best-Case-Komplexität: Dies ist die Komplexität der Lösung des Problems für die beste Eingabe der Größe n.
2. Durchschnittsfallkomplexität: Dies ist die Komplexität der Lösung des Problems im Durchschnitt. Diese Komplexität wird nur in Bezug auf a definiert Wahrscheinlichkeitsverteilung über die Eingänge. Wenn beispielsweise angenommen wird, dass alle Eingaben derselben Größe gleich wahrscheinlich sind, kann die durchschnittliche Fallkomplexität in Bezug auf die gleichmäßige Verteilung über alle Eingaben der Größe definiert werden n.
3. Amortisierte Analyse: Amortisierte Analyse berücksichtigt sowohl den kostspieligen als auch den weniger kostspieligen Betrieb in der gesamten Reihe von Operationen des Algorithmus.
4. Worst-Case-Komplexität: Dies ist die Komplexität der Lösung des Problems für den schlimmsten Eingang der Größe n.

Die Bestellung von billig bis kostspielig ist: am besten, durchschnittlich (von Diskrete einheitliche Verteilung), amortisiert, schlimmste.

Betrachten Sie beispielsweise den deterministischen Sortieralgorithmus schnelle Sorte. Dies löst das Problem der Sortierung einer Liste von Ganzzahlen, die als Eingabe angegeben werden. Der schlimmste Fall ist, wenn der Drehpunkt immer der größte oder kleinste Wert in der Liste ist (daher ist die Liste niemals geteilt). In diesem Fall braucht der Algorithmus Zeit O(n²). Wenn wir davon ausgehen, dass alle möglichen Permutationen der Eingabeliste gleich wahrscheinlich sind, ist die durchschnittliche Zeit für die Sortierung o ((n Protokoll n). Der beste Fall kommt aufn Protokoll n) Zeit.

Ober- und Untergrenze für die Komplexität von Problemen

Um die Berechnungszeit (oder ähnliche Ressourcen wie Raumverbrauch) zu klassifizieren, ist es hilfreich, die oberen und unteren Grenzen nach der maximalen Zeitspanne zu demonstrieren, die für den effizientesten Algorithmus zur Lösung eines bestimmten Problems erforderlich ist. Die Komplexität eines Algorithmus wird normalerweise als die schlimmste Komplexität angesehen, sofern nicht anders angegeben. Die Analyse eines bestimmten Algorithmus fällt unter das Gebiet von Analyse von Algorithmen. Eine Obergrenze zeigen T(n) In der Zeitkomplexität eines Problems muss man nur zeigen, dass es höchstens einen bestimmten Algorithmus gibt T(n). Es ist jedoch viel schwieriger, untere Grenzen nachzuweisen, da die unteren Grenzen eine Aussage über alle möglichen Algorithmen machen, die ein bestimmtes Problem lösen. Der Ausdruck "Alle möglichen Algorithmen" enthält nicht nur die heute bekannten Algorithmen, sondern auch jeden Algorithmus, der in Zukunft entdeckt werden könnte. Eine untere Grenze von zeigen T(n) Für ein Problem muss zeigen T(n).

Ober- und Untergrenzen werden normalerweise mit dem angegeben Big O Notation, was ständige Faktoren und kleinere Begriffe verbirgt. Dies macht die Grenzen unabhängig von den spezifischen Details des verwendeten Computermodells. Zum Beispiel wenn, wenn T(n) = 7n²+15n+40, in Big O Notation würde man schreiben T(n) = O (n²).

Komplexitätsklassen

Definieren von Komplexitätsklassen

A Komplexitätsklasse ist eine Reihe von Problemen der damit verbundenen Komplexität. Einfachere Komplexitätsklassen werden durch die folgenden Faktoren definiert:

• Die Art des Rechenproblems: Die am häufigsten verwendeten Probleme sind Entscheidungsprobleme. Komplexitätsklassen können jedoch basierend auf definiert werden Funktionsprobleme, Probleme zählen, Optimierungsprobleme, Probleme versprechen, etc.
• Das Berechnungsmodell: Das häufigste Berechnungsmodell ist die deterministische Turing-Maschine, aber viele Komplexitätsklassen basieren auf nicht deterministischen Turing-Maschinen. Boolesche Schaltungen, Quanten -Turing -Maschinen, Monotonkreise, etc.
• Die Ressource (oder Ressourcen), die begrenzt und gebunden ist: Diese beiden Eigenschaften werden normalerweise zusammen angegeben, wie z. B. "Polynomzeit", "logarithmischer Raum", "konstante Tiefe" usw.

Einige Komplexitätsklassen haben komplizierte Definitionen, die nicht in diesen Rahmen passen. Somit hat eine typische Komplexitätsklasse eine Definition wie die folgende:

Die Reihe von Entscheidungsproblemen, die durch eine deterministische Turing -Maschine innerhalb der Zeit lösbar sind f(n). (Diese Komplexitätsklasse ist als Time bekannt (f(n)).)

Aber die oben nach einer konkrete Funktion begrenzt die Berechnungszeit f(n) ergibt häufig Komplexitätsklassen, die vom ausgewählten Maschinenmodell abhängen. Zum Beispiel die Sprache {xx | x ist eine binäre String} kann in gelöst werden lineare Zeit Auf einer Multitape-Turing-Maschine, erfordert jedoch notwendigerweise eine quadratische Zeit im Modell von Einzel-Turing-Maschinen. Wenn wir Polynomvariationen in der Laufzeit zulassen, Cobham-Edmonds-These stellt fest, dass "die zeitliche Komplexität in zwei angemessenen und allgemeinen Berechnungsmodellen polynomisch verwandt ist" (Goldreich 2008, Kapitel 1.2). Dies bildet die Grundlage für die Komplexitätsklasse P, das ist die Reihe von Entscheidungsproblemen, die durch eine deterministische Turing -Maschine innerhalb der Polynomzeit lösbar sind. Der entsprechende Satz von Funktionsproblemen ist FP.

Wichtige Komplexitätsklassen

Eine Darstellung der Beziehung zwischen Komplexitätsklassen

Viele wichtige Komplexitätsklassen können definiert werden, indem die Zeit oder den Raum vom Algorithmus begrenzt wird. Einige wichtige Komplexitätsklassen von Entscheidungsproblemen, die auf diese Weise definiert wurden, sind die folgenden:

Die logarithmischen Raumklassen berücksichtigen (notwendigerweise) den für die Darstellung des Problems erforderlichen Raums nicht.

Es stellt sich heraus Savitchs Theorem.

Andere wichtige Komplexitätsklassen umfassen BPP, Zpp und RP, die mit Verwendung definiert werden Probabilistische Turing -Maschinen; AC und NC, die mit booleschen Schaltungen definiert werden; und BQP und QMA, die unter Verwendung von Quanten -Turing -Maschinen definiert werden. #P ist eine wichtige Komplexitätsklasse von Zählproblemen (nicht Entscheidungsprobleme). Klassen wie IP und BIN werden definiert Interaktive Proof -Systeme. ALLE ist die Klasse aller Entscheidungsprobleme.

Hierarchie -Theoreme

Für die auf diese Weise definierten Komplexitätsklassen ist es wünschenswert zu beweisen, dass das Entspannen der Anforderungen an (z. B.) Berechnungszeit tatsächlich eine Reihe größerer Probleme definiert. Insbesondere, obwohl Time (n) ist in Time (Time (n²)) Es wäre interessant zu wissen, ob die Aufnahme streng ist. Für Zeit- und Raumanforderungen wird die Antwort auf solche Fragen durch die Zeit- und Raumhierarchie -Theoreme gegeben. Sie werden als Hierarchie -Theoreme bezeichnet, weil sie eine ordnungsgemäße Hierarchie in den Klassen induzieren, die durch Einschränkung der jeweiligen Ressourcen definiert sind. Somit gibt es Paare von Komplexitätsklassen, so dass eine ordnungsgemäß in den anderen enthalten ist. Nachdem wir solche ordnungsgemäßen Einschlüsse abgeleitet haben, können wir quantitative Aussagen darüber abgeben, wie viel zusätzlicher Zeit oder Platz mehr benötigt werden, um die Anzahl der Probleme zu erhöhen, die gelöst werden können.

Genauer gesagt die Zeithierarchie Theorem besagt, dass

$oder (f (n)) {\ big)}}$.

Das Raumhierarchie Theorem besagt, dass

$oder )){\groß )}}$.

Die Zeit- und Raumhierarchie -Theoreme bilden die Grundlage für die meisten Trennungsergebnisse von Komplexitätsklassen. Zum Beispiel zeigt der Zeithierarchie -Theorem, dass P in der Expime streng enthalten ist und der Raumhierarchie -Theorem uns sagt, dass L streng in PSPACE enthalten ist.

Die Ermäßigung

Viele Komplexitätsklassen werden unter Verwendung des Konzepts einer Reduzierung definiert. Eine Reduzierung ist eine Umwandlung eines Problems in ein anderes Problem. Es erfasst die informelle Vorstellung eines Problems, das höchstens so schwierig ist wie ein weiteres Problem. Zum Beispiel, wenn ein Problem X kann mit einem Algorithmus für gelöst werden Y, X ist nicht schwieriger als Yund wir sagen das X reduziert zu Y. Es gibt viele verschiedene Arten von Reduktionen, basierend auf der Reduktionsmethode, wie z. Polynomzeitreduzierungen oder Log-Raum-Reduzierungen.

Die am häufigsten verwendete Reduktion ist eine Polynomzeitreduktion. Dies bedeutet, dass der Reduktionsprozess Polynomzeit in Anspruch nimmt. Zum Beispiel kann das Problem des Quadrierens einer Ganzzahl auf das Problem der Multiplizierung von zwei Ganzzahlen reduziert werden. Dies bedeutet, dass ein Algorithmus zum Multiplizieren von zwei Ganzzahlen verwendet werden kann, um eine Ganzzahl zu quadrieren. In der Tat kann dies erfolgen, indem beide Eingaben des Multiplikationsalgorithmus gleichermaßen eingegeben werden. Daher sehen wir, dass Quadrat nicht schwieriger als die Multiplikation ist, 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 X ist schwer für eine Klasse von Problemen C Wenn jedes Problem in C kann auf reduziert werden auf X. Somit kein Problem in C ist schwieriger als XSeit einem Algorithmus für X ermöglicht es uns, jedes Problem in C. Der Begriff der harten Probleme hängt von der Art der verwendeten Reduktion ab. Bei Komplexitätsklassen, die größer als P sind, werden häufig Polynomzeitverringerungen verwendet. Insbesondere die Probleme, die für NP schwierig sind, ist der Satz von von Np-harte Probleme.

Wenn ein Problem X ist in C und schwer für C, dann X wird gesagt, dass Komplett zum C. Das bedeutet, dass X ist das schwierigste Problem in C. (Da viele Probleme ebenso schwierig sein könnten, könnte man das sagen X ist eines der schwierigsten Probleme in C.) So die Klasse von NP-Complete Die Probleme enthalten die schwierigsten Probleme in NP, in dem Sinne, dass sie am wahrscheinlichsten nicht in P sind, da das Problem P = NP nicht gelöst ist und in der Lage ist, ein bekanntes NP-Complete-Problem zu verringern, π, π₂, zu einem anderen Problem, π₁würde darauf hinweisen, dass es keine Polynom-Zeit-Lösung für π gibt₁. Dies liegt daran, dass eine Polynom-Zeit-Lösung für π₁ würde eine Polynom-Zeit-Lösung für π liefern₂. In ähnlicher Weise können alle NP -Probleme auf den Satz reduziert werden, um eine zu finden NP-Complete Problem, das in Polynomzeit gelöst werden kann, würde bedeuten, dass p = np.^[3]

Wichtige offene Probleme

Diagramm der Komplexitätsklassen sorgte dafür, dass p ≠ np. Die Existenz von Problemen in NP außerhalb von P und NP-Complete in diesem Fall wurde von Ladner festgelegt.^[4]

P gegen NP -Problem

Die Komplexitätsklasse P wird häufig als mathematische Abstraktionsmodellierung der Rechenaufgaben angesehen, die einen effizienten Algorithmus zulassen. Diese Hypothese wird als die genannt Cobham -Edmonds -These. Die Komplexitätsklasse NpAuf der anderen Seite enthält viele Probleme, die Menschen effizient lösen möchten, für die jedoch kein effizienter Algorithmus bekannt ist, wie der Boolesche Zufriedenheitsproblem, das Hamiltonian Path Problem und die Scheitelpunktabdeckungsproblem. Da deterministische Turing-Maschinen spezielle nicht deterministische Turing-Maschinen sind, ist leicht zu beobachten, dass jedes Problem in P auch Mitglied der Klasse NP ist.

Die Frage, ob P entspricht NP, ist eine der wichtigsten offenen Fragen in der theoretischen Informatik aufgrund der großen Auswirkungen einer Lösung.^[3] Wenn die Antwort ja lautet, können viele wichtige Probleme nachweislich effizientere Lösungen haben. Dazu gehören verschiedene Arten von Ganzzahlprogrammierung Probleme in Unternehmensforschung, viele Probleme in Logistik, Proteinstrukturvorhersage in Biologie,^[5] und die Fähigkeit, formale Beweise von zu finden reine Mathematik Theoreme.^[6] Das P -Vers -NP -Problem ist eines der der Millennium Prize Problems vorgeschlagen von der Clay Mathematics Institute. Es gibt einen Preis in Höhe von 1.000.000 US -Dollar für die Lösung des Problems.^[7]

Probleme in NP, die nicht in P oder NP-Complete bekannt sind

Es wurde von Ladner gezeigt, dass wenn P ≠ Np Dann gibt es Probleme in Np das sind weder in P Noch NP-Complete.^[4] Solche Probleme werden genannt NP-Intermediate Probleme. Das Graph Isomorphismus Problem, das Diskretes Logarithmusproblem und die Ganzzahlfaktorisierungsproblem sind Beispiele für Probleme, von denen angenommen wird, dass sie NP-Intermediate sind. Sie sind einige der wenigen NP -Probleme, in denen nicht bekannt ist, dass sie sich befinden P oder zu sein NP-Complete.

Das Graph Isomorphismus Problem ist das rechnerische Problem der Bestimmung, ob zwei endliche Grafiken sind isomorph. Ein wichtiges ungelöstes Problem in der Komplexitätstheorie ist, ob das Problem der Graph -Isomorphismus in der Fall ist P, NP-Complete, oder NP-Intermediate. Die Antwort ist nicht bekannt, aber es wird angenommen, dass das Problem zumindest nicht die NP-Vervollständigung ist.^[8] Wenn der Graph-Isomorphismus NP-Vervollständigung ist, ist die Polynomzeithierarchie bricht auf seine zweite Ebene zusammen.^[9] Da allgemein angenommen wird, dass die Polynomhierarchie nicht auf ein endliches Niveau kollabiert, wird angenommen, dass das Graph-Isomorphismus keine NP-Vervollständigung ist. Der beste Algorithmus für dieses Problem, weil László Babai und Eugene Luks hat Laufzeit ${\ displayStyle o (2^{\ sqrt {n \ log n}})}$ Für Grafiken mit n Scheitelpunkte, obwohl einige aktuelle Arbeiten von Babai einige potenziell neue Perspektiven dazu bieten.^[10]

Das Ganzzahlfaktorisierungsproblem ist das rechnerische Problem der Bestimmung der Primfaktorisierung einer bestimmten Ganzzahl. Als Entscheidungsproblem formuliert, ist es das Problem der Entscheidung, ob der Eingang einen Hauptfaktor weniger hat als k. Es ist kein effizienter Integer -Faktorisierungsalgorithmus bekannt, und diese Tatsache bildet die Grundlage mehrerer moderner kryptografischer Systeme wie der RSA Algorithmus. Das Problem der Ganzzahlfaktorisierung ist in Np und in Co-NP (und sogar in UP und Co-up^[11]). Wenn das Problem ist NP-CompleteDie Polynomzeithierarchie fällt auf ihre erste Ebene (d. H., Np wird gleich Co-NP). Der bekannteste Algorithmus für die Ganzzahlfaktorisierung ist die Allgemeines Zahlenfeld Sieb, was Zeit braucht ${\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{ \ sqrt [{3}] {(\ log \ log n)^{2}}}})}$^[12] eine seltsame Ganzzahl berücksichtigen n. Allerdings am bekanntesten Quantenalgorithmus Für dieses Problem, Shors Algorithmus, läuft in Polynomzeit. Leider sagt diese Tatsache nicht viel darüber aus, wo das Problem in Bezug auf Nichtquantum-Komplexitätsklassen liegt.

Trennungen zwischen anderen Komplexitätsklassen

Es wird vermutet, dass viele bekannte Komplexitätsklassen ungleich sind, dies wurde jedoch nicht bewiesen. Zum Beispiel P ⊆ Np ⊆ Pp ⊆ PSPACE, aber es ist möglich, dass P = PSPACE. Wenn P ist ungleich zu Np, dann P ist ungleich zu PSPACE entweder. Da gibt es viele Komplexitätsklassen dazwischen P und PSPACE, wie zum Beispiel RP, BPP, Pp, BQP, Ma, PHusw. Es ist möglich, dass all diese Komplexitätsklassen zu einer Klasse zusammenbrechen. Zu beweisen, dass eine dieser Klassen ungleich ist, wäre ein großer Durchbruch in der Komplexitätstheorie.

Auf der gleichen Linie, Co-NP Enthält die Klasse die ergänzen Probleme (d. H. Probleme mit dem Jawohl/nein Antworten umgekehrt) von Np Probleme. Man glaubt^[13] das Np ist ungleich zu Co-NP; Es wurde jedoch noch nicht bewiesen. Es ist klar, dass, wenn diese beiden Komplexitätsklassen dann nicht gleich sind, dann nicht gleich P ist ungleich zu Np, seit P=Polizist. Also wenn P=Np Wir würden haben Polizist=Co-NP woher Np=P=Polizist=Co-NP.

Ebenso ist es nicht bekannt, wenn L (Die Menge aller Probleme, die im logarithmischen Raum gelöst werden können) ist streng enthalten in P oder gleich P. Auch hier gibt es viele Komplexitätsklassen zwischen beiden, wie z. Nl und NC, und es ist nicht bekannt, ob sie unterschiedliche oder gleiche Klassen sind.

Es wird vermutet, dass P und BPP sind gleich. Es ist jedoch derzeit offen, wenn BPP = Nexp.

Uneinheitlichkeit

Ein Problem, das theoretisch gelöst werden kann (z. B. mit großen, aber endlichen Ressourcen, insbesondere Zeit), aber in der Praxis irgendein Lösung nimmt zu viele Ressourcen, um nützlich zu sein, ist als als bekannt unlösbares Problem.^[14] Umgekehrt wird ein Problem, das in der Praxis gelöst werden kann Nachdruckbares Problem, buchstäblich "ein Problem, das behandelt werden kann". Der Begriff undurchführbar (buchstäblich "kann nicht gemacht werden") wird manchmal austauschbar mit verwendet unlösbar,^[15] Obwohl dies die Verwirrung mit a machbare Lösung in Mathematische Optimierung.^[16]

Nachfolgbare Probleme werden häufig mit Problemen mit polynomialen Zeitlösungen identifiziert (P, P -Zeit); Dies ist als die bekannt Cobham -Edmonds -These. Zu den Problemen, die in diesem Sinne unlösbar sind, gehören diejenigen, die es sind Nachfolger-schwer. Wenn NP nicht dasselbe ist wie P, dann Np-harte Probleme sind auch in diesem Sinne unlösbar.

Diese Identifizierung ist jedoch ungenau: Eine Polynom-Zeit-Lösung mit großem Grad oder großem führenden Koeffizienten wächst schnell und kann für praktische Größenprobleme unpraktisch sein. Umgekehrt kann eine exponentielle Lösung, die langsam wächst, bei realistischen Eingaben praktisch sein, oder eine Lösung, die im schlimmsten Fall lange dauert, kann in den meisten Fällen oder im Durchschnittsfall eine kurze Zeit dauern und daher immer noch praktisch sein. Zu sagen, dass ein Problem nicht in P ist, bedeutet nicht, dass alle großen Fälle des Problems schwierig sind oder dass die meisten von ihnen sind. Zum Beispiel das Entscheidungsproblem in Presburger -Arithmetik Es wurde gezeigt, dass es nicht in P ist, aber es wurden Algorithmen geschrieben, die das Problem in den meisten Fällen in angemessenen Zeiten lösen. In ähnlicher Weise können Algorithmen die NP-Complete lösen Rucksackproblem über eine Vielzahl von Größen in weniger als quadratischer Zeit und Sat Solvers Verwandten Sie routinemäßig große Instanzen der NP-Complete Boolesche Zufriedenheitsproblem.

Um zu sehen, warum Exponential-Zeit-Algorithmen in der Praxis im Allgemeinen unbrauchbar sind, sollten Sie ein Programm in Betracht ziehen, das 2 machtⁿ Operationen vor dem Stoppen. Für kleine n, sagen wir 100, und die Annahme zum Beispiel, dass der Computer 10 tut¹² Operationen pro Sekunde würden das Programm für etwa 4 × 10 ausgeführt¹⁰ Jahre, was die gleiche Größenordnung wie die ist Alter des Universums. Selbst mit einem viel schnelleren Computer wäre das Programm nur für sehr kleine Fälle nützlich, und in diesem Sinne ist die Unverschämtheit eines Problems etwas unabhängig vom technologischen Fortschritt. Ein exponentieller Zeitalgorithmus, der 1.0001 dauertⁿ Operationen sind praktisch bis n wird relativ groß.

In ähnlicher Weise ist ein Polynomzeitalgorithmus nicht immer praktisch. Wenn seine Laufzeit beispielsweise ist n¹⁵Es ist unangemessen, es effizient zu betrachten, und es ist immer noch nutzlos, außer in kleinen Fällen. In der Tat sogar in der Praxis n³ oder n² Algorithmen sind in realistischen Problemgrößen oft unpraktisch.

Kontinuierliche Komplexitätstheorie

Die kontinuierliche Komplexitätstheorie kann auf die Komplexitätstheorie von Problemen beziehen numerische Analyse. Ein Ansatz zur Komplexitätstheorie der numerischen Analyse^[17] ist Informationsbasierte Komplexität.

Die kontinuierliche Komplexitätstheorie kann sich auch auf die Komplexitätstheorie der Verwendung von beziehen Analoge Berechnung, was kontinuierlich verwendet Dynamische Systeme und Differentialgleichung.^[18] Kontrolltheorie Kann als Form der Berechnung angesehen werden, und Differentialgleichungen werden bei der Modellierung von kontinuierlichen Zeit- und hybriden diskreten kontinuierlichen Zeitsystemen verwendet.^[19]

Geschichte

Ein frühes Beispiel für die Analyse der Algorithmuskomplexität ist die Laufzeitanalyse des Euklidischer Algorithmus gemacht von Gabriel Lamé 1844.

Bevor die tatsächliche Forschung, die sich ausdrücklich der Komplexität von algorithmischen Problemen widmete, begann, wurden von verschiedenen Forschern zahlreiche Grundlagen festgelegt. Am einflussreichsten unter diesen war die Definition von Turing -Maschinen durch Alan Turing 1936, was sich als sehr robuste und flexible Vereinfachung eines Computers herausstellte.

Der Beginn systematischer Studien zur Berechnungskomplexität wird auf das wegweisende Papier von 1965 "über die Computerkomplexität von Algorithmen" nach 1965 zurückgeführt Juris Hartmanis und Richard E. Stearns, die die Definitionen von festgelegt haben Zeitkomplexität und Raumkomplexitätund bewies die Hierarchie -Theoreme.^[20] Außerdem 1965 Edmonds schlug vor, einen "guten" Algorithmus als eine Laufzeit zu betrachten, die durch ein Polynom der Eingangsgröße begrenzt ist.^[21]

Frühere Papiere, die Probleme untersuchten, die durch Turing -Maschinen mit spezifischen begrenzten Ressourcen lösbar sind^[20] John Myhill's Definition von linear begrenzte Automaten (Myhill 1960), Raymond SmullyanDas Studium der rudimentären Sets (1961) sowie von Hisao YamadaPapier^[22] über Echtzeitberechnungen (1962). Etwas früher, Boris Trakhtenbrot (1956) untersuchte ein Pionier auf dem Gebiet der UdSSR eine weitere spezifische Komplexitätsmaßnahme.^[23] Wie er sich erinnert:

[Mein] anfängliches Interesse [in der Automatenheorie] wurde jedoch zunehmend zugunsten der Rechenkomplexität, einer aufregenden Verschmelzung kombinatorischer Methoden, beiseite gelegt Schalttheoriemit dem konzeptionellen Arsenal der Theorie der Algorithmen. Diese Ideen waren mir früher im Jahr 1955 aufgetreten, als ich den Begriff "Signalfunktion" prägte, der heutzutage allgemein als "Komplexitätsmaß" bezeichnet wird.^[24]

1967,, Manuel Blum formuliert einen Satz von Axiome (jetzt bekannt als als Blum -Axiome) Angabe wünschenswerter Eigenschaften von Komplexitätsmessungen auf dem Satz rechenbarer Funktionen und erwies sich als wichtiges Ergebnis, das sogenannte sogenannte Ergebnis Geschwindigkeitssheorem. Das Feld begann 1971 zu florieren, als Stephen Cook und Leonid Levin bewiesen die Existenz praktisch relevanter Probleme, die sind NP-Complete. 1972,, Richard Karp nahm diese Idee mit seinem wegweisenden Papier einen Sprung nach vorne, "Reduzierbarkeit unter kombinatorischen Problemen", in dem er diese 21 unterschiedlichen zeigte Kombinatorisch und Diagramm theoretisch Probleme, die jeweils berüchtigt für seine rechnergestützte Uneinheitlichkeit sind, sind NP-Vervollständigung.^[25]

Siehe auch

Arbeitet zur Komplexität

• Wuppuluri, Shyam; Doria, Francisco A., Hrsg. (2020), Komplexität entwirren: Das Leben und Werk von Gregory Chaitin, Welt wissenschaftlich, doi:10.1142/11270, ISBN 978-981-12-0006-9, S2CID 198790362

Verweise

Zitate

Lehrbücher

• Arora, Sanjeev; Barak, Boaz (2009), Rechenkomplexität: ein moderner Ansatz, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Downey, Rod; Fellows, Michael (1999), Parametrisierte Komplexität, Monographien in Informatik, Berlin, New York: Springer-Verlag, ISBN 9780387948836^{[Permanent Dead Link]}
• Du, Ding-Zhu; KO, Ker-I (2000), Theorie der rechnerischen Komplexität, John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R.; Johnson, David S. (1979), Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung, W. H. Freeman, ISBN 0-7167-1045-5
• Goldreich, Oded (2008), Computerkomplexität: Eine konzeptionelle Perspektive, Cambridge University Press
• Van Leeuwen, Januar, ed. (1990), Handbuch der theoretischen Informatik (Band A): Algorithmen und Komplexität, MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Rechenkomplexität (1. Aufl.), Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), Introduction to the Theory of Computation (2. Aufl.), USA: Thomson -Kurs -Technologie, ISBN 978-0-534-95097-2

Umfragen

• Khalil, Hatem; Ulery, Dana (1976), "Eine Überprüfung der aktuellen Studien zur Komplexität von Algorithmen für partielle Differentialgleichungen", Verfahren der Jahreskonferenz zu - ACM 76, ACM '76: 197–201, doi:10.1145/800191.805573, ISBN 9781450374897, S2CID 15497394
• Kochen, Stephen (1983), "Ein Überblick über die Computerkomplexität", Kommunieren. ACM, 26 (6): 400–408, doi:10.1145/358141.358144, ISSN 0001-0782, S2CID 14323396
• Fortnow, Lance; Homer, Steven (2003), "Eine kurze Geschichte der rechnerischen Komplexität" (PDF), Bulletin der Eatcs, 80: 95–133
• Mertens, Stephan (2002), "Computerkomplexität für Physiker", Computing in Wissenschaft und Eng., 4 (3): 31–47, Arxiv:cond-mat/0012185, Bibcode:2002cse ..... 4c..31m, doi:10.1109/5992.998639, ISSN 1521-9615, S2CID 633346

Externe Links

• Der Komplexitätszoo
• "Rechenkomplexitätsklassen", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Was sind die wichtigsten Ergebnisse (und Papiere) in der Komplexitätstheorie, die jeder wissen sollte?
• Scott Aaronson: Warum sich Philosophen um die Computerkomplexität kümmern sollten