Rechenbetonte Kompliziertheitstheorie ist ein Zweig der Theorie der Berechnung in der theoretischen Informatik und Mathematik, die sich darauf konzentriert, rechenbetonte Probleme gemäß ihrer innewohnenden Schwierigkeit zu klassifizieren, und jene Klassen mit einander zu verbinden. In diesem Zusammenhang, wie man versteht, ist ein rechenbetontes Problem eine Aufgabe, die im Prinzip dem lösen durch einen Computer zugänglich ist (der grundsätzlich bedeutet, dass das Problem durch eine Reihe mathematischer Instruktionen festgesetzt werden kann). Informell besteht ein rechenbetontes Problem aus Problem-Beispielen und Lösungen dieser Problem-Beispiele. Zum Beispiel, primality Prüfung ist das Problem der Bestimmung, ob eine gegebene Zahl erst ist oder nicht. Die Beispiele dieses Problems sind natürliche Zahlen, und die Lösung eines Beispiels ist ja oder nicht gestützt darauf, ob die Zahl erst ist oder nicht.

Ein Problem wird als von Natur aus schwierig betrachtet, wenn seine Lösung bedeutende Mittel verlangt, was auch immer der Algorithmus verwendet hat. Die Theorie formalisiert diese Intuition, durch das Einführen mathematischer Modelle der Berechnung, um diese Probleme und die Quantitätsbestimmung des Betrags von Mitteln zu studieren, musste sie, wie Zeit und Lagerung lösen. Andere Kompliziertheitsmaßnahmen werden auch, wie der Betrag der Kommunikation (verwendet in der Nachrichtenkompliziertheit), die Zahl von Toren in einem Stromkreis (verwendet in der Stromkreis-Kompliziertheit) und die Zahl von Verarbeitern (verwendet in der Parallele-Computerwissenschaft) verwendet. Eine der Rollen der rechenbetonten Kompliziertheitstheorie ist, die praktischen Grenzen darauf zu bestimmen, welche Computer können und nicht tun können.

Nah verwandte Felder in der theoretischen Informatik sind Analyse von Algorithmen und Berechenbarkeitstheorie. Eine Schlüsselunterscheidung zwischen Analyse von Algorithmen und rechenbetonter Kompliziertheitstheorie ist, dass der erstere dem Analysieren des Betrags von durch einen besonderen Algorithmus erforderlichen Mitteln gewidmet wird, um ein Problem zu beheben, wohingegen der Letztere eine allgemeinere Frage über alle möglichen Algorithmen stellt, die verwendet werden konnten, um dasselbe Problem zu beheben. Genauer versucht es, Probleme zu klassifizieren, die können oder mit passend eingeschränkten Mitteln nicht gelöst werden können. Der Reihe nach, eindrucksvolle Beschränkungen der verfügbaren Mittel ist, was rechenbetonte Kompliziertheit aus der Berechenbarkeitstheorie unterscheidet: Die letzte Theorie fragt, welche Probleme im Prinzip algorithmisch behoben werden können.

Rechenbetonte Probleme

Problem-Beispiele

Ein rechenbetontes Problem kann als eine unendliche Sammlung von Beispielen zusammen mit einer Lösung für jedes Beispiel angesehen werden. Die Eingangsschnur für ein rechenbetontes Problem wird ein Problem-Beispiel genannt, und sollte mit dem Problem selbst nicht verwirrt sein. In der rechenbetonten Kompliziertheitstheorie bezieht sich ein Problem auf die abstrakte Frage, gelöst zu werden. Im Gegensatz ist ein Beispiel dieses Problems eine ziemlich konkrete Äußerung, die als der Eingang für ein Entscheidungsproblem dienen kann. Denken Sie zum Beispiel das Problem der Primality-Prüfung. Das Beispiel ist eine Zahl (z.B 15), und die Lösung ist "ja", wenn die Zahl erst ist und "nein" sonst (in diesem Fall "nein"). Wechselweise ist das Beispiel ein besonderer Eingang zum Problem, und die Lösung ist die Produktion entsprechend dem gegebenen Eingang.

Um weiter den Unterschied zwischen einem Problem und einem Beispiel hervorzuheben, denken Sie das folgende Beispiel der Entscheidungsversion des Handelsreisender-Problems: Gibt es einen Weg in den meisten 2000 Kilometern in der Länge, die alle Deutschlands 15 größten Städte durchführt? Die Antwort auf dieses besondere Problem-Beispiel ist wenig nützlich, um andere Beispiele des Problems, wie das Bitten um eine Hin- und Rückfahrt durch alle Seiten in Mailand zu lösen, dessen Gesamtlänge höchstens 10 km ist. Deshalb richtet Kompliziertheitstheorie rechenbetonte Probleme und nicht besondere Problem-Beispiele.

Das Darstellen von Problem-Beispielen

es rechenbetonte Probleme denkt, ist ein Problem-Beispiel eine Schnur über ein Alphabet. Gewöhnlich wird das Alphabet genommen, um das binäre Alphabet (d. h., der Satz {0,1}) zu sein, und so sind die Schnuren bitstrings. Als in einem wirklichen Computer müssen mathematische Gegenstände außer bitstrings angemessen verschlüsselt werden. Zum Beispiel können ganze Zahlen in der binären Notation vertreten werden, und Graphen können direkt über ihr Angrenzen matrices, oder durch die Verschlüsselung ihrer Angrenzen-Listen in der Dualzahl verschlüsselt werden.

Wenn auch einige Beweise von mit der Kompliziertheit theoretischen Lehrsätzen regelmäßig etwas konkrete Wahl der Eingangsverschlüsselung annehmen, versucht man, die Diskussion Auszug genug zu halten, um der Wahl der Verschlüsselung unabhängig zu sein. Das kann durch das Sicherstellen erreicht werden, dass verschiedene Darstellungen in einander effizient umgestaltet werden können.

Entscheidungsprobleme als formelle Sprachen

Entscheidungsprobleme sind einer der Hauptgegenstände der Studie in der rechenbetonten Kompliziertheitstheorie. Ein Entscheidungsproblem ist ein spezieller Typ des rechenbetonten Problems, dessen Antwort entweder ja oder nein, oder abwechselnd entweder 1 oder 0 ist. Ein Entscheidungsproblem kann als eine formelle Sprache angesehen werden, wo die Mitglieder der Sprache Beispiele sind, deren Antwort ist Ja, und die Nichtmitglieder jene Beispiele sind, deren Produktion nein ist. Das Ziel ist, mithilfe von einem Algorithmus zu entscheiden, ob eine gegebene eingegebene Schnur ein Mitglied der formellen Sprache unter der Rücksicht ist. Wenn der Algorithmus, dieses Problem entscheidend, die Antwort zurückgibt, Ja, wie man sagt, akzeptiert der Algorithmus die Eingangsschnur, sonst, wie man sagt, weist es den Eingang zurück.

Ein Beispiel eines Entscheidungsproblems ist das folgende. Der Eingang ist ein willkürlicher Graph. Das Problem besteht im Entscheiden, ob der gegebene Graph verbunden wird, oder nicht. Die formelle mit diesem Entscheidungsproblem vereinigte Sprache ist dann der Satz aller verbundenen Graphen natürlich, um eine genaue Definition dieser Sprache zu erhalten, man muss entscheiden, wie Graphen als binäre Schnuren verschlüsselt werden.

Funktionsprobleme

Ein Funktionsproblem ist ein rechenbetontes Problem, wo eine einzelne Produktion (einer Gesamtfunktion) für jeden Eingang erwartet wird, aber die Produktion ist komplizierter als dieses eines Entscheidungsproblems, d. h. ist es nicht gerade ja oder nein. Bemerkenswerte Beispiele schließen das Handelsreisender-Problem und die ganze Zahl factorization Problem ein.

Es ist verführerisch zu denken, dass der Begriff von Funktionsproblemen viel reicher ist als der Begriff von Entscheidungsproblemen. Jedoch ist das nicht wirklich der Fall, da Funktionsprobleme als Entscheidungsprobleme umgearbeitet werden können. Zum Beispiel kann die Multiplikation von zwei ganzen Zahlen ausgedrückt werden, weil sich der Satz dessen (a, b, c) solch verdreifacht, dass die Beziehung ein × b = c hält. Das Entscheiden, ob ein gegebener dreifacher Mitglied dieses Satzes ist, entspricht dem Beheben des Problems, zwei Zahlen zu multiplizieren.

Das Messen der Größe eines Beispiels

Um die Schwierigkeit zu messen, ein rechenbetontes Problem zu beheben, könnte man sehen mögen, wie viel Zeit der beste Algorithmus verlangt, um das Problem zu beheben. Jedoch kann die Laufzeit im Allgemeinen vom Beispiel abhängen. Insbesondere größere Beispiele werden verlangen, dass mehr Zeit löst. So wird die Zeit, die erforderlich ist, ein Problem (oder der Raum zu beheben, erforderlich, oder jedes Maß der Kompliziertheit) als Funktion der Größe des Beispiels berechnet. Das wird gewöhnlich genommen, um die Größe des Eingangs in Bit zu sein. Kompliziertheitstheorie interessiert sich dafür, wie Algorithmen mit einer Zunahme in der Eingangsgröße klettern. Zum Beispiel, im Problem der Entdeckung, ob ein Graph verbunden wird, wie viel mehr Zeit braucht man, um ein Problem für einen Graphen mit 2n Scheitelpunkte im Vergleich zur Zeit zu beheben, die für einen Graphen mit n Scheitelpunkten genommen ist?

Wenn die Eingangsgröße n ist, kann die genommene Zeit als eine Funktion von n ausgedrückt werden. Seit der übernommenen Zeit können verschiedene Eingänge derselben Größe verschieden sein, die Grenzfall-Zeitkompliziertheit T (n) wird definiert, um die maximale Zeit übernommen alle Eingänge der Größe n zu sein. Wenn T (n) ein Polynom in n ist, dann, wie man sagt, ist der Algorithmus ein polynomischer Zeitalgorithmus. Die These von Cobham sagt, dass ein Problem mit einem ausführbaren Betrag von Mitteln behoben werden kann, wenn es einen polynomischen Zeitalgorithmus zulässt.

Maschinenmodelle und Kompliziertheitsmaßnahmen

Turing Maschine

Eine Turing Maschine ist ein mathematisches Modell einer allgemeinen Rechenmaschine. Es ist ein theoretisches Gerät, das auf einem Streifen des Bandes enthaltene Symbole manipuliert. Maschinen von Turing sind als eine praktische Rechentechnologie, aber eher als ein Gedanke-Experiment nicht beabsichtigt, das eine Rechenmaschine vertritt. Es wird geglaubt, dass, wenn ein Problem durch einen Algorithmus behoben werden kann, dort eine Maschine von Turing besteht, die das Problem behebt. Tatsächlich ist das die Behauptung der Kirch-Turing-These. Außerdem ist es bekannt, dass alles, was auf anderen Modellen der Berechnung geschätzt werden kann, die uns heute, wie eine RAM-Maschine, das Spiel von Conway des Lebens, der Zellautomaten oder jeder Programmiersprache bekannt ist, auf einer Maschine von Turing geschätzt werden kann. Da Turing Maschinen leicht sind, mathematisch zu analysieren und geglaubt werden, so stark zu sein, wie jedes andere Modell der Berechnung, ist die Maschine von Turing das meistens verwendete Modell in der Kompliziertheitstheorie.

Viele Typen von Maschinen von Turing werden verwendet, um Kompliziertheitsklassen, wie deterministische Maschinen von Turing, probabilistic Maschinen von Turing, nichtdeterministische Maschinen von Turing, Quant Maschinen von Turing, symmetrische Maschinen von Turing und Wechselmaschinen von Turing zu definieren. Sie sind alle im Prinzip ebenso stark, aber wenn Mittel (wie Zeit oder Raum) begrenzt werden, können einige von diesen stärker sein als andere.

Eine deterministische Maschine von Turing ist die grundlegendste Maschine von Turing, die ein festes Regelwerk verwendet, um seine zukünftigen Handlungen zu bestimmen. Eine probabilistic Maschine von Turing ist eine deterministische Maschine von Turing mit einer Extraversorgung von zufälligen Bit. Die Fähigkeit, probabilistic Entscheidungen zu treffen, hilft häufig Algorithmen, Probleme effizienter zu beheben. Algorithmen, die zufällige Bit verwenden, werden randomized Algorithmen genannt. Eine nichtdeterministische Maschine von Turing ist eine deterministische Maschine von Turing mit einem Komfortmerkmal des Nichtdeterminismus, der einer Maschine von Turing erlaubt, vielfache mögliche zukünftige Handlungen von einem gegebenen Staat zu haben. Eine Weise, Nichtdeterminismus anzusehen, besteht darin, dass die Maschinenzweige von Turing in viele mögliche rechenbetonte Pfade an jedem Schritt, und wenn es das Problem in einigen dieser Zweige behebt, wie man sagt, hat es das Problem behoben. Klar wird dieses Modell nicht gemeint, um ein physisch realisierbares Modell zu sein, es ist gerade eine theoretisch interessante abstrakte Maschine, die besonders interessante Kompliziertheitsklassen verursacht. Für Beispiele, sieh nichtdeterministischen Algorithmus.

Andere Maschinenmodelle

Viele Maschinenmodelle, die vom Standardmehrband Maschinen von Turing verschieden sind, sind in der Literatur, zum Beispiel zufällige Zugriffsmaschinen vorgeschlagen worden. Vielleicht überraschend kann jedes dieser Modelle zu einem anderen umgewandelt werden, ohne jede rechenbetonte Extramacht zur Verfügung zu stellen. Die Zeit und der Speicherverbrauch dieser abwechselnden Modelle können sich ändern. Was alle diese Modelle haben, gemeinsam ist, dass die Maschinen deterministisch funktionieren.

Jedoch sind einige rechenbetonte Probleme leichter, in Bezug auf ungewöhnlichere Mittel zu analysieren. Zum Beispiel ist eine nichtdeterministische Maschine von Turing ein rechenbetontes Modell, dem erlaubt wird sich auszubreiten, um viele verschiedene Möglichkeiten sofort zu überprüfen. Die nichtdeterministische Maschine von Turing ist sehr wenig verbunden, wie wir physisch Algorithmen schätzen wollen, aber sein Ausbreiten gewinnt genau viele der mathematischen Modelle, die wir analysieren wollen, so dass nichtdeterministische Zeit eine sehr wichtige Quelle im Analysieren rechenbetonter Probleme ist.

Kompliziertheitsmaßnahmen

Für eine genaue Definition dessen, was es bedeutet, ein Problem mit einer gegebenen Zeitdauer und Raum zu beheben, wird ein rechenbetontes Modell wie die deterministische Maschine von Turing verwendet. Die Zeit, die durch eine deterministische Maschine von Turing erforderlich ist, die M auf dem Eingang x ist die Gesamtzahl von Zustandübergängen oder Schritte, die Maschine, macht, bevor es hinkt und Produktionen die Antwort ("ja" oder "nein"). Wie man sagt, funktioniert eine Turing MaschinenM innerhalb der Zeit f (n), wenn die Zeit, die durch die M auf jedem Eingang der Länge n erforderlich ist, am grössten Teil von f (n) ist. Ein Entscheidungsproblem A kann rechtzeitig f (n) behoben werden, wenn dort eine Maschine von Turing besteht, die rechtzeitig f (n) funktioniert, der das Problem behebt. Da sich Kompliziertheitstheorie für das Klassifizieren von auf ihrer Schwierigkeit gestützten Problemen interessiert, definiert man Sätze von auf einigen Kriterien gestützten Problemen. Zum Beispiel wird der Satz von Problemen, die innerhalb der Zeit f (n) auf einer deterministischen Maschine von Turing lösbar sind, dann durch DTIME (f (n)) angezeigt.

Analoge Definitionen können für Raumvoraussetzungen gemacht werden. Obwohl Zeit und Raum die wohl bekanntesten Kompliziertheitsmittel ist, kann jedes Kompliziertheitsmaß als eine rechenbetonte Quelle angesehen werden. Kompliziertheitsmaßnahmen werden sehr allgemein durch die Kompliziertheitsaxiome von Blum definiert. Andere in der Kompliziertheitstheorie verwendete Kompliziertheitsmaßnahmen schließen Nachrichtenkompliziertheit, Stromkreis-Kompliziertheit und Entscheidungsbaum-Kompliziertheit ein.

Beste, schlechteste und durchschnittliche Fall-Kompliziertheit

Die beste, schlechteste und durchschnittliche Fall-Kompliziertheit bezieht sich auf drei verschiedene Weisen, die Zeitkompliziertheit (oder jedes andere Kompliziertheitsmaß) von verschiedenen Eingängen derselben Größe zu messen. Seit einigen Eingängen der Größe kann n schneller sein, um zu lösen, als andere, wir definieren die folgenden Kompliziertheiten:

• Kompliziertheit des besten Falls: Das ist die Kompliziertheit, das Problem für den besten Eingang der Größe n zu beheben.
• Grenzfall-Kompliziertheit: Das ist die Kompliziertheit, das Problem für den schlechtesten Eingang der Größe n zu beheben.
• Kompliziertheit des durchschnittlichen Falls: Das ist die Kompliziertheit, das Problem durchschnittlich zu beheben. Diese Kompliziertheit wird nur in Bezug auf einen Wahrscheinlichkeitsvertrieb über die Eingänge definiert. Zum Beispiel, wenn, wie man annimmt, alle Eingänge derselben Größe ebenso wahrscheinlich erscheinen, kann die durchschnittliche Fall-Kompliziertheit in Bezug auf die Rechteckverteilung über alle Eingänge der Größe n definiert werden.

Betrachten Sie zum Beispiel den dc als das Sortieren der Algorithmus-Schnellsortierung. Das behebt das Problem, eine Liste von ganzen Zahlen zu sortieren, die als der Eingang gegeben wird. Der Grenzfall ist, wenn der Eingang sortiert oder in umgekehrter Reihenfolge sortiert wird, und der Algorithmus O (n) für diesen Fall Zeit in Anspruch nimmt. Wenn wir annehmen, dass alle möglichen Versetzungen der Eingangsliste ebenso wahrscheinlich sind, ist die durchschnittliche für das Sortieren genommene Zeit O (n loggen n). Der beste Fall kommt vor, wenn jedes Drehen die Liste entzweit, auch O (n brauchend, loggen n) Zeit.

Obere und niedrigere Grenzen auf der Kompliziertheit von Problemen

Um die Berechnungszeit (oder ähnliche Mittel, wie Raumverbrauch) zu klassifizieren, interessiert man sich für den Beweis oberer und niedrigerer Grenzen auf der minimalen Zeitdauer, die durch den effizientesten Algorithmus erforderlich ist, der ein gegebenes Problem behebt. Die Kompliziertheit eines Algorithmus wird gewöhnlich genommen, um seine Grenzfall-Kompliziertheit, wenn nicht angegeben, sonst zu sein. Das Analysieren eines besonderen Algorithmus fällt unter dem Feld der Analyse von Algorithmen. Einen oberen zu zeigen, hat T (n) auf der Zeitkompliziertheit eines Problems gebunden, man muss nur zeigen, dass es einen besonderen Algorithmus mit der Laufzeit am grössten Teil von T (n) gibt. Jedoch ist Beweis niedrigerer Grenzen viel schwieriger, da niedrigere Grenzen eine Erklärung über alle möglichen Algorithmen abgeben, die ein gegebenes Problem beheben. Der Ausdruck "alle möglichen Algorithmen" schließt nicht nur die Algorithmen bekannt heute ein, aber jeder Algorithmus, der in der Zukunft entdeckt werden könnte. Einen niedrigeren zu zeigen, der T (n) für ein Problem gebunden ist, verlangt Vertretung, dass kein Algorithmus Zeitkompliziertheit tiefer haben kann als T (n).

Obere und niedrigere Grenzen werden gewöhnlich mit der großen O Notation festgesetzt, die unveränderliche Faktoren und kleinere Begriffe verbirgt. Das macht die Grenzen unabhängig der spezifischen Details des rechenbetonten verwendeten Modells. Zum Beispiel, wenn T (n) = 7n + 15n + 40, in der großen O Notation man T (n) = O (n) schreiben würde.

Kompliziertheitsklassen

Das Definieren von Kompliziertheitsklassen

Eine Kompliziertheitsklasse ist eine Reihe von Problemen der zusammenhängenden Kompliziertheit. Einfachere Kompliziertheitsklassen werden durch die folgenden Faktoren definiert:

• Der Typ des rechenbetonten Problems: Die meistens verwendeten Probleme sind Entscheidungsprobleme. Jedoch können Kompliziertheitsklassen gestützt auf Funktionsproblemen definiert werden, Probleme, Optimierungsprobleme, Versprechungsprobleme usw. aufzählend.
• Das Modell der Berechnung: Das allgemeinste Modell der Berechnung ist die deterministische Maschine von Turing, aber viele Kompliziertheitsklassen basieren auf nichtdeterministischen Maschinen von Turing, Stromkreisen von Boolean, Quant Maschinen von Turing, Eintönigkeitsstromkreise usw.
• Die Quelle (oder Mittel), die begrenzt werden und die Grenzen: Diese zwei Eigenschaften werden gewöhnlich zusammen, wie "polynomische Zeit", "logarithmischer Raum", "unveränderliche Tiefe" usw. festgesetzt.

Natürlich haben einige Kompliziertheitsklassen komplizierte Definitionen, die dieses Fachwerk nicht einbauen. So hat eine typische Kompliziertheitsklasse eine Definition wie der folgende:

:The-Satz von Entscheidungsproblemen, die durch eine deterministische Maschine von Turing innerhalb der Zeit f (n) lösbar sind. (Diese Kompliziertheitsklasse ist als DTIME (f (n)) bekannt.)

Aber das Springen der Berechnungszeit oben nach etwas konkreter Funktion f (n) gibt häufig Kompliziertheitsklassen nach, die vom gewählten Maschinenmodell abhängen. Zum Beispiel ist die Sprache {xx | x jede binäre Schnur} kann in der geradlinigen Zeit auf einem Mehrband Maschine von Turing gelöst werden, aber verlangt notwendigerweise quadratische Zeit mit dem Modell des einzelnen Bandes Maschinen von Turing. Wenn wir polynomische Schwankungen in der Laufzeit erlauben, stellt These von Cobham-Edmonds fest, dass "die Zeitkompliziertheiten in irgendwelchen zwei angemessenen und allgemeinen Modellen der Berechnung polynomisch verbunden sind". Das bildet die Basis für die Kompliziertheitsklasse P, die der Satz von Entscheidungsproblemen ist, die durch eine deterministische Maschine von Turing innerhalb der polynomischen Zeit lösbar sind. Der entsprechende Satz von Funktionsproblemen ist FP.

Wichtige Kompliziertheitsklassen

Viele wichtige Kompliziertheitsklassen können durch das Springen der Zeit oder des durch den Algorithmus verwendeten Raums definiert werden. Einige wichtige Kompliziertheitsklassen von auf diese Weise definierten Entscheidungsproblemen sind der folgende:

Es stellt sich dass PSPACE = NPSPACE und EXPSPACE = NEXPSPACE durch den Lehrsatz von Savitch heraus.

Andere wichtige Kompliziertheitsklassen schließen BPP, ZPP und RP ein, die mit probabilistic Maschinen von Turing definiert werden; AC und NC, die mit Stromkreisen von Boolean und BQP und QMA definiert werden, die mit dem Quant Maschinen von Turing definiert werden. #P ist eine wichtige Kompliziertheitsklasse des Zählens von Problemen (nicht Entscheidungsprobleme). Klassen wie IP und AM werden mit Interaktiven Probesystemen definiert. ALLES ist die Klasse aller Entscheidungsprobleme.

Hierarchie-Lehrsätze

Für die Kompliziertheitsklassen definiert auf diese Weise ist es wünschenswert zu beweisen, dass das Entspannen der Voraussetzungen daran (sagt), dass Berechnungszeit tatsächlich einen größeren Satz von Problemen definiert. Insbesondere obwohl DTIME (n) in DTIME (n) enthalten wird, würde es interessant sein zu wissen, ob die Einschließung streng ist. Für Voraussetzungen der Zeit und Raums wird die Antwort auf solche Fragen zu dieser Zeit und Raumhierarchie-Lehrsätze beziehungsweise gegeben. Sie werden Hierarchie-Lehrsätze genannt, weil sie eine richtige Hierarchie auf den definierten Klassen veranlassen, indem sie die jeweiligen Mittel beschränken. So gibt es Paare von solchen Kompliziertheitsklassen, dass einer in den anderen richtig eingeschlossen wird. Solche richtigen Satz-Einschließungen abgeleitet, können wir fortfahren, quantitative Erklärungen darüber abzugeben, wie viel mehr zusätzliche Zeit oder Raum erforderlich sind, um die Zahl von Problemen zu steigern, die gelöst werden können.

Genauer setzt der Zeithierarchie-Lehrsatz das fest

Der Raumhierarchie-Lehrsatz setzt das fest

Die Hierarchie-Lehrsätze der Zeit und Raums bilden die Basis für die meisten Trennungsergebnisse von Kompliziertheitsklassen. Zum Beispiel sagt der Zeithierarchie-Lehrsatz uns, dass P in EXPTIME ausschließlich enthalten wird, und der Raumhierarchie-Lehrsatz uns sagt, dass L in PSPACE ausschließlich enthalten wird.

Die Verminderung

Viele Kompliziertheitsklassen werden mit dem Konzept der Verminderung definiert. Die Verminderung ist eine Transformation eines Problems in ein anderes Problem. Es gewinnt den informellen Begriff eines Problems, das mindestens so schwierig ist wie ein anderes Problem. Zum Beispiel, wenn ein Problem X mit einem Algorithmus für Y behoben werden kann, X ist nicht schwieriger als Y, und wir sagen, dass X zu Y abnimmt. Es gibt viele verschiedene Typen der Verminderungen, die auf der Methode der Verminderung, wie die Koch-Verminderungen, die Verminderungen von Karp und die Verminderungen von Levin und das gebundene die Kompliziertheit der Verminderungen, wie die polynomisch-maligen Verminderungen oder die mit dem Klotzraumverminderungen gestützt sind.

Die meistens verwendete Verminderung ist die polynomisch-malige Verminderung. Das bedeutet, dass der Verminderungsprozess Zeit in Anspruch nimmt. Zum Beispiel kann das Problem des Quadrierens eine ganze Zahl auf das Problem reduziert werden, zwei ganze Zahlen zu multiplizieren. Das bedeutet, dass ein Algorithmus, um zwei ganze Zahlen zu multiplizieren, an das Quadrat eine ganze Zahl gewöhnt sein kann. Tatsächlich kann das durch das Geben desselben Eingangs beiden Eingängen des Multiplikationsalgorithmus getan werden. So sehen wir, dass Quadrieren nicht schwieriger ist als Multiplikation, da Quadrieren auf die Multiplikation reduziert werden kann.

Das motiviert das Konzept eines Problems, das für eine Kompliziertheitsklasse hart ist. Ein Problem X ist für eine Klasse von Problemen C hart, wenn jedes Problem in C auf X reduziert werden kann. So ist kein Problem in C härter als X, da ein Algorithmus für X uns erlaubt, jedes Problem in C zu beheben. Natürlich hängt der Begriff von harten Problemen vom Typ der Verminderung ab, die wird verwendet. Für Kompliziertheitsklassen, die größer sind als P, werden die polynomisch-maligen Verminderungen allgemein verwendet. Insbesondere der Satz von Problemen, die für NP hart sind, ist der Satz von NP-hard Problemen.

Wenn ein Problem X in C und hart für C ist, dann X wird gesagt, für C abgeschlossen zu sein. Das bedeutet, dass X das härteste Problem in C. ist (Seitdem viele Probleme ebenso hart sein konnten, könnte man sagen, dass X eines der härtesten Probleme in C. ist) So, enthält die Klasse von NP-complete Problemen die schwierigsten Probleme in NP im Sinn, dass sie diejenigen sind, um am wahrscheinlichsten in P nicht zu sein. Weil das Problem P = NP nicht gelöst wird, im Stande seiend, ein bekanntes NP-complete Problem, Π, zu einem anderen Problem, Π zu reduzieren, würde anzeigen, dass es keine bekannte polynomisch-malige Lösung für Π gibt. Das ist, weil eine polynomisch-malige Lösung von Π eine polynomisch-malige Lösung von Π nachgeben würde. Ähnlich, weil alle NP Probleme auf den Satz reduziert werden können, ein NP-complete Problem findend, das in der polynomischen Zeit gelöst werden kann, würde das P = NP bedeuten.

Wichtige offene Probleme

P gegen das NP Problem

Die Kompliziertheitsklasse P wird häufig als eine mathematische Abstraktion gesehen, jene rechenbetonten Aufgaben modellierend, die einen effizienten Algorithmus zulassen. Diese Hypothese wird die These von Cobham-Edmonds genannt. Der Kompliziertheitsklassen-NP enthält andererseits viele Probleme, die Leute gern effizient beheben würden, aber für den kein effizienter Algorithmus, wie das Problem von Boolean satisfiability, das Pfad-Problem von Hamiltonian und das Scheitelpunkt-Deckel-Problem bekannt ist. Da deterministische Maschinen von Turing spezielle nichtdeterministische Maschinen von Turing sind, wird es leicht bemerkt, dass jedes Problem in P auch Mitglied der Klasse NP ist.

Die Frage dessen, ob P NP gleichkommt, ist eine der wichtigsten geöffneten Fragen in der theoretischen Informatik wegen der breiten Implikationen einer Lösung. Wenn die Antwort ist, Ja, wie man zeigen kann, haben viele wichtige Probleme effizientere Lösungen. Diese schließen verschiedene Typen von Programmierproblemen der ganzen Zahl in der Operationsforschung, vielen Problemen in der Logistik, Protein-Struktur-Vorhersage in der Biologie und der Fähigkeit ein, formelle Beweise von reinen Mathematik-Lehrsätzen zu finden. Der P gegen das NP Problem ist eines der vom Tonmathematik-Institut vorgeschlagenen Millennium-Preis-Probleme. Es gibt einen Preis von 1,000,000 US$, für das Problem aufzulösen.

Probleme in NP, der nicht bekannt ist, in P oder NP-complete zu sein

Es wurde von Ladner dass gezeigt, wenn P  NP dann dort Probleme in NP bestehen, die weder in P noch in NP-complete sind. Solche Probleme werden NP-Zwischenprobleme genannt. Das Graph-Isomorphismus-Problem, das getrennte Logarithmus-Problem und die ganze Zahl factorization Problem sind Beispiele von Problemen, die geglaubt sind, NP-Zwischenglied zu sein. Sie sind einige der sehr wenigen NP Probleme, die nicht bekannt sind, in P zu sein oder NP-complete zu sein.

Das Graph-Isomorphismus-Problem ist das rechenbetonte Problem der Bestimmung, ob zwei begrenzte Graphen isomorph sind. Ein wichtiges ungelöstes Problem in der Kompliziertheitstheorie besteht darin, ob das Graph-Isomorphismus-Problem in P, NP-complete oder NP-Zwischenglied ist. Die Antwort ist nicht bekannt, aber es wird geglaubt, dass das Problem mindestens nicht NP-complete ist. Wenn Graph-Isomorphismus NP-complete, die polynomischen Zeithierarchie-Zusammenbrüche zu seinem zweiten Niveau ist. Da es weit geglaubt wird, dass die polynomische Hierarchie zu keinem begrenzten Niveau zusammenbricht, wird es geglaubt, dass Graph-Isomorphismus nicht NP-complete ist. Der beste Algorithmus für dieses Problem, wegen Laszlo Babais und Eugene Luks hat Durchlaufzeit 2 für Graphen mit n Scheitelpunkten.

Die ganze Zahl factorization Problem ist das rechenbetonte Problem, den ersten factorization einer gegebenen ganzen Zahl zu bestimmen. Ausgedrückt als ein Entscheidungsproblem ist es das Problem des Entscheidens, ob der Eingang einen Faktor weniger hat als k. Keine effiziente ganze Zahl factorization Algorithmus ist bekannt, und diese Tatsache bildet die Basis von mehreren modernen kryptografischen Systemen wie der RSA Algorithmus. Die ganze Zahl factorization Problem ist in NP und in co-NP (und sogar in und Staatsstreich). Wenn das Problem NP-complete ist, wird die polynomische Zeithierarchie zu seinem ersten Niveau zusammenbrechen (d. h. NP wird co-NP gleichkommen). Der am besten bekannte Algorithmus für die ganze Zahl factorization ist das allgemeine Sieb des numerischen Feldes, das O (e) zum Faktor eine ganze N-Bit-Zahl Zeit in Anspruch nimmt. Jedoch läuft der am besten bekannte Quant-Algorithmus für dieses Problem, der Algorithmus von Shor, wirklich in der polynomischen Zeit. Leider sagt diese Tatsache viel darüber nicht, wo das Problem in Bezug auf Nichtquant-Kompliziertheitsklassen liegt.

Trennungen zwischen anderen Kompliziertheitsklassen

verdächtigt, sind viele bekannte Kompliziertheitsklassen ungleich, aber das ist nicht bewiesen worden. Zum Beispiel P  NP  SEITEN  PSPACE, aber ist es das P = PSPACE möglich. Wenn P NP nicht gleich ist, dann ist P PSPACE auch nicht gleich. Da es viele bekannte Kompliziertheitsklassen zwischen P und PSPACE, wie RP, BPP, SEITEN, BQP, Magister artium, PH usw. gibt, ist es möglich, dass alle diese Kompliziertheitsklassen zu einer Klasse zusammenbrechen. Der Beweis, dass einige dieser Klassen ungleich ist, würde ein Hauptdurchbruch in der Kompliziertheitstheorie sein.

Entlang denselben Linien ist co-NP die Klasse, die die Ergänzungsprobleme (d. h. Probleme mit ja/no Antworten umgekehrt) von NP Problemen enthält. Es wird geglaubt, dass NP co-NP nicht gleich ist; jedoch ist es noch nicht bewiesen worden. Es ist gezeigt worden, dass, wenn diese zwei Kompliziertheitsklassen dann nicht gleich sind, P NP nicht gleich ist.

Ähnlich ist es nicht bekannt, ob L (der Satz aller Probleme, die im logarithmischen Raum gelöst werden können) in P ausschließlich enthalten oder zu P gleich wird. Wieder gibt es viele Kompliziertheitsklassen zwischen den zwei, wie NL und NC, und es ist nicht bekannt, ob sie verschiedene oder gleiche Klassen sind.

Es wird vermutet, dass P und BPP gleich sind. Jedoch ist es zurzeit wenn BPP = NEXP offen.

Hartnäckigkeit

Probleme, die in der Theorie (z.B, in Anbetracht der unendlichen Zeit) gelöst werden können, aber die in der Praxis auch nehmen, sehnen sich nach ihren Lösungen, nützlich zu sein, sind als unnachgiebige Probleme bekannt. In der Kompliziertheitstheorie, wie man betrachtet, sind Probleme, die an polynomisch-maligen Lösungen Mangel haben, für mehr unnachgiebig als die kleinsten Eingänge. Tatsächlich stellt die These von Cobham-Edmonds fest, dass nur jene Probleme, die in der polynomischen Zeit gelöst werden können, auf einem rechenbetonten Gerät durchführbar geschätzt werden können. Probleme, die, wie man bekannt, in diesem Sinn unnachgiebig sind, schließen diejenigen ein, die EXPTIME-hart sind. Wenn NP nicht dasselbe als P ist, dann sind die NP-complete Probleme auch in diesem Sinn unnachgiebig. Um zu sehen, warum exponentialmalige Algorithmen in der Praxis unbrauchbar sein könnten, denken Sie ein Programm, das 2 Operationen vor dem Halt macht. Für kleinen n, sagen Sie 100, und das Annehmen wegen des Beispiels, dass der Computer 10 Operationen jede Sekunde tut, würde das Programm für ungefähr 4 × 10 Jahre führen, der grob das Alter des Weltalls ist. Sogar mit einem viel schnelleren Computer würde das Programm nur für sehr kleine Beispiele nützlich sein, und in diesem Sinn ist die Hartnäckigkeit eines Problems des technischen Fortschritts etwas unabhängig. Dennoch ist ein polynomischer Zeitalgorithmus nicht immer praktisch. Wenn seine Laufzeit, sagen wir, n ist, ist es unvernünftig, es als effizient zu betrachten, und es ist noch außer auf kleinen Beispielen nutzlos.

Welches Hartnäckigkeitsmittel in der Praxis für die Debatte offen ist. Der Ausspruch, dass ein Problem nicht in P ist, deutet nicht an, dass alle großen Fälle des Problems hart sind, oder sogar dass die meisten von ihnen sind. Zum Beispiel, wie man gezeigt hat, ist das Entscheidungsproblem in der Arithmetik von Presburger in P nicht gewesen, noch sind Algorithmen geschrieben worden, die das Problem in angemessenen Fristen in den meisten Fällen beheben. Ähnlich können Algorithmen das NP-complete Rucksack-Problem über eine breite Reihe von Größen in weniger beheben, als quadratische Zeit und GESESSENER solvers alltäglich große Beispiele des NP-complete Boolean satisfiability Problem behandeln.

Dauernde Kompliziertheitstheorie

Dauernde Kompliziertheitstheorie kann sich auf die Kompliziertheitstheorie von Problemen beziehen, die dauernde Funktionen einschließen, denen durch discretizations, wie studiert, in der numerischen Analyse näher gekommen wird. Eine Annäherung an die Kompliziertheitstheorie der numerischen Analyse ist gestützte Kompliziertheit der Information.

Dauernde Kompliziertheitstheorie kann sich auch auf die Kompliziertheitstheorie des Gebrauches der analogen Berechnung beziehen, die dauernde dynamische Systeme und Differenzialgleichungen verwendet. Steuerungstheorie kann als eine Form der Berechnung betrachtet werden, und Differenzialgleichungen werden im Modellieren von dauernd-maligen und hybriden Systemen "getrennte dauernde Zeit" verwendet.

Geschichte

Bevor die wirkliche der Kompliziertheit von algorithmischen Problemen ausführlich gewidmete Forschung angefangen hat, wurden zahlreiche Fundamente von verschiedenen Forschern angelegt. Am einflussreichsten unter diesen war die Definition von Maschinen von Turing durch Alan Turing 1936, der sich erwiesen hat, ein sehr robuster und flexibler Begriff des Computers zu sein.

datieren Sie auf den Anfang von systematischen Studien in der rechenbetonten Kompliziertheit zum Samenpapier "Auf der Rechenbetonten Kompliziertheit von Algorithmen" durch Juris Hartmanis und Richard Stearns (1965), der die Definitionen der Kompliziertheit der Zeit und Raums angelegt hat und die Hierarchie-Lehrsätze bewiesen hat.

Gemäß schließen frühere Papiere, die Probleme studieren, die durch Maschinen von Turing mit spezifischen begrenzten Mitteln lösbar sind, die Definition von John Myhill von geradlinigen begrenzten Automaten (Myhill 1960), die Studie von Raymond Smullyan von rudimentären Sätzen (1961), sowie das Papier von Hisao Yamada auf der Echtzeitberechnung (1962) ein. Etwas früher hat Boris Trakhtenbrot (1956), ein Pionier im Feld von der UDSSR, ein anderes spezifisches Kompliziertheitsmaß studiert. Weil er sich erinnert:

1967 hat Manuel Blum eine axiomatische Kompliziertheitstheorie entwickelt, die auf seinen Axiomen gestützt ist, und hat ein wichtiges Ergebnis, den so genannten, Beschleunigungslehrsatz bewiesen. Das Feld hat wirklich begonnen zu gedeihen, als der amerikanische Forscher Stephen Cook und, unabhängig, Leonid Levin in der UDSSR arbeitend, bewiesen hat, dass dort praktisch relevante Probleme bestehen, die NP-complete sind. 1972 hat Richard Karp diese Idee ein Sprung vorwärts mit seinem merklichen Papier genommen, "Reducibility Unter Kombinatorischen Problemen", in dem er gezeigt hat, dass 21 verschiedene kombinatorische und Graph theoretische Probleme, jeder, der für seine rechenbetonte Hartnäckigkeit berüchtigt ist, NP-complete sind.

Siehe auch

• Liste der Berechenbarkeit und Kompliziertheitsthemen
• Liste von wichtigen Veröffentlichungen in der theoretischen Informatik
• Ungelöste Probleme in der Informatik
• Liste von Kompliziertheitsklassen
• Strukturkompliziertheitstheorie
• Beschreibende Kompliziertheitstheorie
• Quant-Kompliziertheitstheorie
• Zusammenhang der rechenbetonten Kompliziertheit
• Parametrisierte Kompliziertheit
• Spielkompliziertheit
• Probekompliziertheit
• Problem von Transcomputational

Referenzen

Lehrbücher

Überblicke

Links

• Der Kompliziertheitszoo