Zeitkomplexität

Diagramme von Funktionen, die üblicherweise in der verwendet werden Analyse von Algorithmen, zeigen die Anzahl der Operationen N Als Ergebnis der Eingangsgröße n Für jede Funktion

Im Informatik, das Zeitkomplexität ist der Rechenkomplexität Das beschreibt die Menge an Computerzeit, die zum Ausführen eines benötigt wird Algorithmus. Die Zeitkomplexität wird üblicherweise durch Zählen der Anzahl der vom Algorithmus ausgeführten elementaren Operationen geschätzt, da jeder Elementarbetrieb eine feste Ausführung in Anspruch nimmt. Daher wird die Zeitspanne und die Anzahl der vom Algorithmus ausgeführten Elementaroperationen als mit a in Verbindung gebracht constant factor.

Da die Laufzeit eines Algorithmus zwischen verschiedenen Eingaben derselben Größe variieren kann, berücksichtigt man üblicherweise die Schlechteste Zeitkomplexität, das ist die maximale Zeit, die für Eingaben einer bestimmten Größe erforderlich ist. Weniger häufig und normalerweise explizit angegeben ist das Durchschnittsfallkomplexität, was der Durchschnitt der Zeit ist, die für Eingaben einer bestimmten Größe benötigt wird (dies ist sinnvoll, da nur eine endliche Anzahl möglicher Eingaben einer bestimmten Größe vorhanden ist). In beiden Fällen wird die zeitliche Komplexität im Allgemeinen als ausgedrückt Funktion der Größe des Eingangs.[1]: 226 Da diese Funktion im Allgemeinen schwer zu berechnen ist und die Laufzeit für kleine Eingaben normalerweise nicht konsequent ist, konzentriert man sich normalerweise auf das Verhalten der Komplexität, wenn die Eingabegröße zunimmt - dh die asymptotisches Verhalten der Komplexität. Daher wird die zeitliche Komplexität üblicherweise verwendet Big O Notation, normalerweise , , , , usw., wo n ist die Größe in Einheiten von Bits benötigt, um die Eingabe darzustellen.

Algorithmische Komplexitäten werden nach der Art der Funktion klassifiziert, die in der großen O -Notation auftritt. Zum Beispiel ein Algorithmus mit zeitlicher Komplexität ist ein Linearer Zeitalgorithmus und ein Algorithmus mit zeitlicher Komplexität für einige Konstante ist ein Polynomzeitalgorithmus.

Tabelle der gemeinsamen Zeitkomplexität

Die folgende Tabelle fasst einige Klassen von allgemein auftretenden Zeitkomplexitäten zusammen. In der Tabelle, Poly (x) = xO(1), d.h. Polynom inx.

Name Komplexitätsklasse Laufzeit (T(n)) Beispiele für Laufzeiten Beispielalgorithmen
ständige Zeit 10 Finden des Medianwerts in einem sortierten Array Zahlen

Berechnung (–1)n

Inverse Ackermann Zeit Abgeschriebene Zeit pro Betrieb mit a disjunkt SET
Iteratiertes logarithmisch Zeit Verteilte Färbung von Zyklen
log-logarithmisch Amortisierte die Zeit pro Operation mit einem begrenzten Prioritätswarteschlange[2]
logarithmische Zeit Dlogime , Binäre Suche
Polylogarithmische Zeit
Bruchkraft wo , Suche in a KD-Baum
lineare Zeit n, Finden Sie den kleinsten oder größten Gegenstand in einem Unsortierten Array, Kadanes Algorithmus, Lineare Suche
"N log-stern n" Zeit Seidel's Polygon -Triangulation Algorithmus.
linearithmische Zeit , Am schnellsten möglich Vergleichsart; Schnelle Fourier-Transformation.
Quasilinearzeit
Quadratische Zeit Blasenart; Sortieren durch Einfügen; Direkte Faltung
Kubikzeit Naive Multiplikation von zwei Matrizen. Berechnung teilweise Korrelation.
Polynomzeit P , Karmarkars Algorithmus zum Lineares Programmieren; ASS -Primalitätstest[3][4]
Quasi-Polynomzeit QP , Wohlbekannt O(Protokoll2n)-Näherungsalgorithmus für die gerichtete Steiner Baumproblem.
Subexponentialzeit
(erste Definition)
Subexp für alle Enthält BPP Es sei denn, dass Expime (siehe unten) gleich Ma.[5]
Subexponentialzeit
(zweite Definition)
Der bekannteste Algorithmus zum Ganzzahlfaktorisierung; Früher der beste Algorithmus für Graph Isomorphismus
Exponentialzeit
(mit linearem Exponent)
E , Lösen des Problem mit reisenden Verkäufern Verwendung Dynamische Programmierung
Exponentialzeit Nachfolger , Lösung Matrixkette Multiplikation über Brute-Force-Suche
faktorielle Zeit Lösen des Problem mit reisenden Verkäufern über Brute-Force-Suche
Doppelte Exponentialzeit 2-Exptime Entscheidung über die Wahrheit einer bestimmten Aussage in Presburger -Arithmetik

Ständige Zeit

Ein Algorithmus soll sein ständige Zeit (auch geschrieben als Zeit) Wenn der Wert von wird durch einen Wert begrenzt, der nicht von der Größe der Eingabe abhängt. Zum Beispiel auf ein einzelnes Element in einem zugreifen Array braucht ständige Zeit als nur einer Betrieb muss durchgeführt werden, um es zu finden. In ähnlicher Weise finden Sie den minimalen Wert in einem Array, der in aufsteigender Reihenfolge sortiert ist. Es ist das erste Element. Das Finden des minimalen Wertes in einem ungeordneten Array ist jedoch kein konstanter Zeitvorgang als Scannen über jeden Element Im Array ist erforderlich, um den minimalen Wert zu bestimmen. Daher ist es ein linearer Zeitbetrieb, der nimmt Zeit. Wenn die Anzahl der Elemente im Voraus bekannt ist und sich jedoch nicht ändert, kann ein solcher Algorithmus immer noch in ständiger Zeit laufen.

Trotz des Namens "konstanter Zeit" muss die Laufzeit nicht unabhängig von der Problemgröße sein, aber eine Obergrenze für die Laufzeit muss unabhängig von der Problemgröße sein. Zum Beispiel die Aufgabe "tauschen Sie die Werte aus a und b falls nötig so wird als konstante Zeit bezeichnet, obwohl die Zeit davon abhängt, ob es bereits wahr ist oder nicht . Es gibt jedoch einige Konstante t so dass die erforderliche Zeit immer ist maximal t.

Hier sind einige Beispiele für Codefragmente, die in konstanter Zeit ausgeführt werden:

int index = 5; int item = list [index];wenn (Bedingung wahr) dann     Führen Sie einen Operation durch, der in konstanter Zeit ausgeführt wirdandersFühren Sie einen anderen Betrieb aus, der in konstanter Zeit ausgeführt wirdzum I = 1 zu 100  zum J = 1 zu 200 führen einen Betrieb aus, der in konstanter Zeit ausgeführt wird

Wenn ist , wo a ist ein konstanter Wert, dies entspricht und in der Standardnotation als angegeben als Sein .

Logarithmische Zeit

Ein Algorithmus soll nehmen logarithmische Zeit Wenn . Seit und werden von a verwandt konstanter Multiplikatorund so so Multiplikator ist irrelevant Zur großen O-Klassifizierung ist die Standardverwendung für logarithmische Zeitalgorithmen unabhängig von der Basis des Logarithmus, der im Ausdruck von auftritt T.

Algorithmen, die logarithmische Zeit nehmen Binärbäume oder bei Verwendung binäre Suche.

Ein Der Algorithmus wird als hocheffizient angesehen, da das Verhältnis der Anzahl der Operationen zur Größe des Eingangs abnimmt und zu Null kommt, wenn n steigt. Ein Algorithmus, der auf alle Elemente seiner Eingabe zugreifen muss n ist von der Reihenfolge von n.

Ein Beispiel für die logarithmische Zeit wird durch die Wörterbuchsuche gegeben. Betrachten Sie a Wörterbuch D was beinhaltet n Einträge, sortiert nach alphabetischer Reihenfolge. Wir nehmen das an, für , man kann auf die zugreifen kTH Eintritt des Wörterbuchs in einer ständigen Zeit. Lassen bezeichnen das kdann versuche es. Unter diesen Hypothesen den Test, um zu sehen, ob ein Wort w IST im Wörterbuch kann in logarithmischer Zeit erfolgen: Überlegen Sie , wo bezeichnet die Bodenfunktion. Wenn Dann sind wir fertig. Sonst wenn Setzen Sie die Suche in der linken Hälfte des Wörterbuchs auf die gleiche Weise fort, andernfalls fahren Sie mit der rechten Hälfte des Wörterbuchs ähnlich fort. Dieser Algorithmus ähnelt der Methode, die häufig verwendet wird, um einen Eintrag in einem Papierwörterbuch zu finden.

Polylogarithmische Zeit

Ein Algorithmus soll hereinlaufen Polylogarithmic Zeit Wenn es Zeit ist ist für einige Konstante k. Eine andere Möglichkeit, dies zu schreiben, ist .

Zum Beispiel, Matrix -Kettenbestellung kann in polylogarithmischer Zeit auf a gelöst werden Parallele Zufallszugriffsmaschine,[6] und ein Graph kann sein entschlossen, planar zu sein in einem Volldynamisch Eingang Zeit pro Einfügen/Löschen.[7]

Sublineare Zeit

Ein Algorithmus soll hereinlaufen Sublineare Zeit (oft geschrieben Sublinearzeit) wenn . Insbesondere umfasst dies Algorithmen mit den oben definierten zeitlichen Komplexitäten.

Typische Algorithmen, die genau sind und dennoch in sublinearer Zeit verwendet werden Parallelverarbeitung (als die NC1 Die Matrixdeterminante berechnet) oder haben alternativ garantierte Annahmen in der Eingabestruktur (als logarithmische Zeit binäre Suche und viele Baumwartungsalgorithmen). Jedoch, formelle Sprachen wie die Menge aller Zeichenfolgen, die eine 1-Bit in der von der ersten angegebenen Position haben Bits der Zeichenfolge können von jedem Bit der Eingabe abhängen und dennoch in sublinearer Zeit berechnet werden.

Der spezifische Begriff Sublinear -Zeitalgorithmus ist in der Regel Algorithmen reserviert, die anders sind als oben, als sie über klassische Serienmaschinenmodelle ausgeführt werden und keine vorherigen Annahmen für die Eingabe zulässig sind.[8] Sie dürfen es jedoch sein zufälligund muss in der Tat für alle außer den trivialsten Aufgaben randomisiert werden.

Ein solcher Algorithmus muss eine Antwort geben, ohne die gesamte Eingabe zu lesen, seine Einzelheiten hängen stark vom Zugang zur Eingabe ab. Normalerweise für einen Eingang, der als binäre Zeichenfolge dargestellt wird Es wird angenommen, dass der Algorithmus rechtzeitig kann anfordern und den Wert von erhalten für jeden i.

Sublineare Zeitalgorithmen sind typischerweise randomisiert und nur bereitstellen ungefähr Lösungen. Tatsächlich kann die Eigenschaft einer binären Schnur mit nur Nullen (und niemandem) leicht als nicht entzündbar durch einen (nicht angesehenen) sublinearen Zeitalgorithmus erwiesen werden. Sublineare Zeitalgorithmen ergeben sich natürlich bei der Untersuchung von Immobilientests.

Lineare Zeit

Ein Algorithmus soll nehmen lineare Zeit, oder Zeit, wenn seine Zeit Komplexität ist . Informell bedeutet dies, dass die Laufzeit mit der Größe des Eingangs höchst linear ansteigt. Genauer gesagt bedeutet dies, dass es eine Konstante gibt c so dass die Laufzeit höchstens ist Für jeden Eingang der Größe n. Beispielsweise erfordert eine Prozedur, die alle Elemente einer Liste addiert, Zeit proportional zur Länge der Liste, wenn die Hinzufügungszeit konstant ist oder zumindest durch eine Konstante begrenzt ist.

Die lineare Zeit ist die bestmögliche Zeitkomplexität in Situationen, in denen der Algorithmus seine gesamte Eingabe nacheinander lesen muss. Daher wurde viel Untersuchungen in die Entdeckung von Algorithmen investiert, die lineare Zeit oder zumindest nahezu linearer Zeit aufweisen. Diese Forschung umfasst sowohl Software- als auch Hardware -Methoden. Es gibt mehrere Hardware -Technologien, die ausbeuten Parallelität Um dies bereitzustellen. Ein Beispiel ist Inhaltsadressible Speicher. Dieses Konzept der linearen Zeit wird in String -Matching -Algorithmen wie dem verwendet Boyer -Moore -Algorithmus und Ukkonens Algorithmus.

Quasilinearzeit

Ein Algorithmus soll hereinlaufen Quasilinearzeit (auch bezeichnet als logarithmische Zeit) wenn für eine positive Konstante k;[9] linearithmische Zeit ist der Fall .[10] Verwendung weiche o Notation Diese Algorithmen sind . Quasilinear -Zeitalgorithmen sind auch für jede Konstante und so schneller als jeder Polynomzeitalgorithmus, dessen Zeitgebunden einen Begriff enthält für jeden .

Zu den Algorithmen, die in der Quasilinearzeit ausgeführt werden, gehören:

  • In-Place-Zusammenführungsart,
  • Schnelle Sorte, hat in seiner randomisierten Version eine Laufzeit in Erwartung der Worst-Case-Eingabe. Die nicht randomisierte Version hat eine Laufzeit nur bei Betrachtung der durchschnittlichen Fallkomplexität.
  • Haufen, , Zusammenführen, sortieren, Introsort, binäre Baumart, SmoothSort, Geduldsortierungusw. im schlimmsten Fall
  • Fast Fourier transformiert,
  • Monge Array Berechnung,

In vielen Fällen die Die Laufzeit ist einfach das Ergebnis einer Ausführung a Betrieb n Zeiten (für die Notation, siehe Big O Notation § Familie von Bachmann -Landau Notationen). Zum Beispiel, Binärbaum -Sortierung erstellt a Binärbaum durch Einfügen jedes Elements der n-GRAUME eins nach dem anderen. Seit der Einfügungsoperation auf a selbstausgleichender binärer Suchbaum nimmt Zeit dauert der gesamte Algorithmus Zeit.

Vergleichsarten zumindest benötigen Vergleiche im schlimmsten Fall, weil , durch Stirlings Annäherung. Sie entstehen auch häufig aus dem Rezidivbeziehung .

Subquadratische Zeit

Ein Algorithmus wird gesagt, dass Subquadratische Zeit wenn .

Zum Beispiel einfach, vergleichsbasiert Sortieren von Algorithmen sind quadratisch (z. Sortieren durch Einfügen), aber fortgeschrittenere Algorithmen finden sich subquadratisch (z. Shell -Sortierung). Keine allgemeinen Sorten in der linearen Zeit, aber die Änderung von quadratisch zu subquadratisch ist von großer praktischer Bedeutung.

Polynomzeit

Ein Algorithmus soll von sein Polynomzeit Wenn seine Laufzeit ist Obergrenze durch eine Polynom Ausdruck in der Größe des Eingangs für den Algorithmus, dh,, T(n) = O(nk) für eine positive Konstante k.[1][11] Probleme für den ein deterministischer Polynomzeitalgorithmus vorhanden ist Komplexitätsklasse P, was im Bereich von zentral ist Computerkomplexitätstheorie. Cobhams These Gibt an, dass die Polynomzeit ein Synonym für "Tractable", "machbar", "effizient" oder "schnell" ist.[12]

Einige Beispiele für Polynomzeitalgorithmen:

  • Das Auswahlsorten Sortieren von Algorithmus weiter n Ganzzahlen leisten Operationen für einige Konstante A. So läuft es in der Zeit und ist ein Polynomzeitalgorithmus.
  • Alle grundlegenden arithmetischen Operationen (Zugabe, Subtraktion, Multiplikation, Teilung und Vergleich) können in Polynomzeit durchgeführt werden.
  • Maximale Übereinstimmungen in Grafiken kann in Polynomzeit gefunden werden.

Stark und schwach polynomiale Zeit

In einigen Kontexten, besonders in Optimierungman unterscheidet zwischen starke polynomiale Zeit und schwach polynomiale Zeit Algorithmen. Diese beiden Konzepte sind nur relevant, wenn die Eingaben zu den Algorithmen aus Ganzzahlen bestehen.

Im arithmetischen Berechnungsmodell wird stark polynomiale Zeit definiert. In diesem Berechnungsmodell sind die grundlegenden arithmetischen Operationen (Zugabe, Subtraktion, Multiplikation, Teilung und Vergleich) unabhängig von den Größen der Operanden einen Zeitschritt der Einheit, um eine Zeitschritts -Zeit zu erzielen. Der Algorithmus läuft in stark polynomialer Zeit, wenn:[13]

  1. Die Anzahl der Operationen im arithmetischen Berechnungsmodell wird durch ein Polynom in der Anzahl der Ganzzahlen in der Eingabeinstanz begrenzt. und
  2. Der vom Algorithmus verwendete Raum wird durch ein Polynom in der Größe des Eingangs begrenzt.

Jeder Algorithmus mit diesen beiden Eigenschaften kann durch Ersetzen der arithmetischen Operationen durch geeignete Algorithmen zur Durchführung der arithmetischen Operationen auf einem in einen Polynomzeitalgorithmus umgewandelt werden Turing Maschine. Die zweite Bedingung ist ausschließlich notwendig: Angesichts der Ganzzahl (was Platz proportional zu nimmt zu n Im Turing Machine -Modell) ist es möglich, zu berechnen mit n Multiplikationen mit wiederholtes Quadrat. Der Raum, der zur Darstellung verwendet wird ist proportional zu und damit eher exponentiell als Polynom im Raum, der zur Darstellung der Eingabe verwendet wird. Daher ist es nicht möglich, diese Berechnung in der Polynomzeit auf einer Turing -Maschine durchzuführen, aber es ist möglich, sie durch polynomial viele arithmetische Operationen zu berechnen.

Für die erste Bedingung gibt es jedoch Algorithmen, die in einer Reihe von Turing-Maschinenschritten ausgeführt werden, die durch ein Polynom in der Länge des binär kodierten Eingangs begrenzt sind, jedoch keine Anzahl von arithmetischen Operationen nutzen, die von einem Polynom in der Anzahl der Eingaben begrenzt sind Zahlen. Das Euklidischer Algorithmus zum Berechnen der größter gemeinsamer Teiler von zwei Ganzzahlen ist ein Beispiel. Mit zwei Ganzzahlen und Der Algorithmus führt zu arithmetische Operationen auf Zahlen mit höchstens Bits. Gleichzeitig kann die Anzahl der arithmetischen Operationen nicht durch die Anzahl der Ganzzahlen im Eingang begrenzt werden (was in diesem Fall konstant ist, gibt es immer nur zwei Ganzzahlen im Eingang). Aufgrund der letzteren Beobachtung verläuft der Algorithmus nicht in stark polynomieller Zeit. Die wirkliche Laufzeit hängt davon ab logarithmisch auf die Größen von und (Das heißt, auf ihrer Länge in Bits) und nicht nur auf der Anzahl der Ganzzahlen in der Eingabe.

Ein Algorithmus, der in der Polynomzeit läuft, aber nicht stark Polynom schwach polynomiale Zeit.[14] Ein bekanntes Beispiel für ein Problem, für das ein schwach polynomieller Zeitalgorithmus bekannt ist, der jedoch nicht bekannt ist, dass ein stark polynomieller Zeitalgorithmus zugibt, ist jedoch Lineares Programmieren. Schwach polynomiale Zeit sollte nicht mit verwechselt werden Pseudopolynomzeit, was hängt linear über die Größe der Werte im Problem und ist nicht wirklich polynomiale Zeit.

Komplexitätsklassen

Das Konzept der Polynomzeit führt zu verschiedenen Komplexitätsklassen in der Computerkomplexitätstheorie. Einige wichtige Klassen, die mit der Polynomzeit definiert sind, sind die folgenden.

  • P: Das Komplexitätsklasse von Entscheidungsprobleme das kann auf a gelöst werden deterministische Turing -Maschine in Polynomzeit
  • Np: Die Komplexitätsklasse von Entscheidungsproblemen, die auf a gelöst werden können Nichtdeterministische Turing-Maschine in Polynomzeit
  • Zpp: Die Komplexitätsklasse von Entscheidungsproblemen, die mit Nullfehler auf a gelöst werden können Probabilistische Turing -Maschine in Polynomzeit
  • RP: Die Komplexitätsklasse von Entscheidungsproblemen, die in der Polynomzeit mit 1-seitigem Fehler auf einer probabilistischen Turing-Maschine gelöst werden können.
  • BPP: Die Komplexitätsklasse von Entscheidungsproblemen, die mit 2-seitigem Fehler auf einer probabilistischen Turing-Maschine in der Polynomzeit gelöst werden können
  • BQP: Die Komplexitätsklasse von Entscheidungsproblemen, die mit 2-seitigem Fehler auf a gelöst werden können Quanten -Turing -Maschine in Polynomzeit

P ist die kleinste Zeitkomplexitätsklasse auf einer deterministischen Maschine, die ist robust In Bezug auf die Änderungen des Maschinenmodells. (Zum Beispiel kann eine Änderung von einer einzelnen Turing-Maschine zu einer Multitape-Maschine zu einer quadratischen Beschleunigung führen, aber jeder Algorithmus, der in der Polynomzeit unter einem Modell läuft abstrakte Maschine Wird eine Komplexitätsklasse haben, die den Problemen entspricht, die in der Polynomzeit auf dieser Maschine gelöst werden können.

Superpolynomzeit

Ein Algorithmus wird definiert, um zu nehmen Superpolynomzeit wenn T(n) wird nicht von einem Polynom begrenzt. Verwendung kleine Omega -Notation, es ist ω(nc) Zeit für alle Konstanten c, wo n ist der Eingabeparameter, typischerweise die Anzahl der Bits im Eingang.

Zum Beispiel ein Algorithmus, der für 2 läuftn Schritte zu einem Eingang der Größe n erfordert eine superpolynomiale Zeit (genauer gesagt, exponentielle Zeit).

Ein Algorithmus, der exponentielle Ressourcen verwendet, ist eindeutig superpolynomisch, aber einige Algorithmen sind nur sehr schwach superpolynomisch. Zum Beispiel die Adleman -Pomerance -Rum -Primalitätstest läuft für nO(Protokollprotokoll n) Zeit läuft n-biteingänge; Dies wächst schneller als jedes Polynom für groß genug nAber die Eingangsgröße muss unpraktisch groß werden, bevor sie nicht von einem Polynom mit geringem Grad dominiert werden kann.

Ein Algorithmus, der eine superpolynomiale Zeit erfordert Komplexitätsklasse P. Cobhams These Setzt, dass diese Algorithmen unpraktisch sind und in vielen Fällen. Seit der P gegen NP -Problem ist ungelöst, es ist nicht bekannt, ob NP-Complete Probleme erfordern eine superpolynomiale Zeit.

Quasi-Polynomzeit

Quasi-Polynomzeit Algorithmen sind Algorithmen, die länger als die Polynomzeit laufen, aber nicht so lange, wie es eine exponentielle Zeit ist. Der schlimmste Fall der Laufzeit eines quasipolynomialen Zeitalgorithmus ist für einige fest . Zum Wir bekommen einen Polynomzeitalgorithmus für Wir bekommen einen sublinearischen Zeitalgorithmus.

Quasi-polynomiale Zeitalgorithmen entstehen typischerweise in Reduzierungen von einem Np-harte Problem zu einem anderen Problem. Zum Beispiel kann man beispielsweise eine Instanz eines NP -harten Problems annehmen 3satund konvertieren es in eine Instanz eines anderen Problems B, aber die Größe der Instanz wird . In diesem Fall beweist diese Reduzierung nicht, dass Problem B NP-HARD ist; Diese Reduktion zeigt nur, dass es für B keinen Polynomzeitalgorithmus gibt, es sei denn Np). In ähnlicher Weise gibt es einige Probleme, für die wir quasi-polynomiale Zeitalgorithmen kennen, aber es ist kein Polynomzeitalgorithmus bekannt. Solche Probleme ergeben sich in Approximationsalgorithmen; Ein berühmtes Beispiel ist das gerichtete Steiner Baumproblem, für die es einen quasipolynomialen Zeitnäherungsalgorithmus gibt, der einen Annäherungsfaktor von erreicht (n Es ist ein offenes Problem, die Anzahl der Eckpunkte zu sein, aber die Existenz eines solchen Polynomzeitalgorithmus zeigt.

Andere Rechenprobleme mit quasipolynomialen Zeitlösungen, aber keine bekannte Polynomzeitlösung umfassen die gepflanzt Clique Problem, bei dem das Ziel ist Finden Sie eine große Clique in der Vereinigung einer Clique und a Zufällige Grafik. Obwohl quasi polynomial lösbar, wurde vermutet, dass das gepflanzte Clique-Problem keine Polynomzeitlösung aufweist. Diese gepflanzte Clique -Vermutung wurde als verwendet Berechnungshärte Annahme um die Schwierigkeit mehrerer anderer Probleme im Rechenproblemen zu beweisen Spieltheorie, Immobilientests, und maschinelles Lernen.[15]

Die Komplexitätsklasse QP besteht aus allen Problemen mit quasipolynomialen Zeitalgorithmen. Es kann in Bezug auf definiert werden Time folgendermaßen.[16]

Beziehung zu NP-Completen-Problemen

In der Komplexitätstheorie die ungelösten P gegen NP Das Problem fragt, ob alle Probleme in NP Polynomzeitalgorithmen aufweisen. All die bekanntesten Algorithmen für NP-Complete Probleme wie 3sat usw. nehmen sich exponentiell. In der Tat wird es für viele natürliche NP-Complete-Probleme vermutet, dass sie keine Subexponential-Zeitalgorithmen haben. Hier bedeutet "Subexponentialzeit" die nachstehend dargestellte zweite Definition. (Andererseits sind viele Diagrammprobleme, die auf natürliche Weise durch Adjazenzmatrizen dargestellt werden bekannt als Exponentialzeithypothese.[17] Da vermutet wird, dass NP-Complete-Probleme keine quasi-polynomialen Zeitalgorithmen aufweisen, resultiert einige unangemessen Näherungsalgorithmen Nehmen Sie an, dass NP-Complete-Probleme keine quasi-polynomialen Zeitalgorithmen aufweisen. Siehe beispielsweise die bekannten Unangemessenheitsergebnisse für die Deckung festlegen Problem.

Subexponentialzeit

Der Begriff Subexponential Zeit wird verwendet, um auszudrücken, dass die Laufzeit eines Algorithmus schneller wachsen kann als jedes Polynom, aber immer noch signifikant kleiner als ein Exponential. In diesem Sinne sind Probleme, die Subexponential-Zeitalgorithmen aufweisen, etwas nachvollziehbarer als solche, die nur exponentielle Algorithmen haben. Die genaue Definition von "Subexponential" ist nicht allgemein vereinbart,[18] Und wir listen die beiden am häufigsten verwendeten unten auf.

Erste Definition

Ein Problem soll subexponentiell lösbar sein, wenn es in Laufzeiten gelöst werden kann, deren Logarithmen kleiner werden als jedes bestimmte Polynom. Genauer ε > 0 Es gibt einen Algorithmus, der das Problem rechtzeitig löst O(2nε). Die Menge aller dieser Probleme ist die Komplexitätsklasse Subexp was in Bezug auf definiert werden kann Time folgendermaßen.[5][19][20][21]

Dieser Begriff des Subexponentials ist in Bezug auf ungleichmäßig ε in dem Sinne, dass ε ist nicht Teil der Eingabe und jedes ε kann seinen eigenen Algorithmus für das Problem haben.

Zweite Definition

Einige Autoren definieren die Subexponentialzeit als Laufzeiten in .[17][22][23] Diese Definition ermöglicht größere Laufzeiten als die erste Definition der Subexponentialzeit. Ein Beispiel für einen solchen Subexponential-Zeitalgorithmus ist der bekannteste klassische Algorithmus für die ganzzahlige Faktorisierung, die Allgemeines Zahlenfeld Sieb, was rechtzeitig über läuft , wo die Länge des Eingangs ist n. Ein anderes Beispiel war das Graph Isomorphismus Problem, was der bekannteste Algorithmus von 1982 bis 2016 gelöst hat . Allerdings bei Stoc 2016 wurde ein quasipolynomialer Zeitalgorithmus vorgestellt.[24]

Es macht einen Unterschied, ob der Algorithmus in der Größe der Instanz, der Anzahl der Scheitelpunkte oder der Anzahl der Kanten subexponentiell sein darf. Im Parametrisierte KomplexitätDieser Unterschied wird explizit gemacht, indem Paare in Betracht gezogen werden von Entscheidungsprobleme und Parameter k. Subept ist die Klasse aller parametrisierten Probleme, die in der Zeit unter dem Exponential in der Zeit ausgeführt werden k und Polynom in der Eingangsgröße n:[25]

Genauer gesagt ist Subept die Klasse aller parametrisierten Probleme für die es a gibt berechnungsbare Funktion mit und ein Algorithmus, der entscheidet L rechtzeitig .

Exponentialzeithypothese

Das Exponentialzeithypothese (Eth) ist das 3sat, das Erfüllbarkeitsproblem von booleschen Formeln in Konjunktive normale Form mit höchstens drei Literale pro Klausel und mit n Variablen können nicht mit der Zeit 2 gelöst werdeno(n). Genauer gesagt ist die Hypothese, dass es einige absolute Konstante gibt c > 0 so dass 3SAT nicht rechtzeitig entschieden werden kann 2CN durch jede deterministische Turing -Maschine. Mit m ETH äquivalent der Hypothese, die die Anzahl der Klauseln bezeichnet, die der Hypothese entspricht, dass kSAT kann nicht in der Zeit 2 gelöst werden 2o(m) für jede ganze Zahl k ≥ 3.[26] Die Exponentialzeithypothese impliziert P ≠ np.

Exponentialzeit

Ein Algorithmus soll sein Exponentialzeit, wenn T(n) wird durch 2 Obergrenze begrenztPoly (n), wo Poly (n) ist ein Polynom in n. Einen Algorithmus ist eine exponentielle Zeit, wenn formaler, wenn T(n) wird durch begrenzt O(2nk) für eine Konstante k. Probleme, die exponentielle Zeitalgorithmen auf einer deterministischen Turing -Maschine zugeben, bilden die Komplexitätsklasse, die als bekannt ist Exp.

Manchmal wird die Exponentialzeit verwendet, um auf Algorithmen zu beziehen, die haben T(n) = 2O(n), wo der Exponent höchstens eine lineare Funktion von ist n. Dies führt zur Komplexitätsklasse E.

Faktorielle Zeit

Ein Algorithmus soll sein faktorielle Zeit wenn T (n) wird von der Obergrenze begrenzt faktorielle Funktion n!. Die faktorielle Zeit ist eine Teilmenge der Exponentialzeit (Exp), weil für alle . Es ist jedoch keine Untergruppe von E.

Ein Beispiel für einen Algorithmus, der in der faktoriellen Zeit ausgeführt wird, ist Bogosort, ein notorisch ineffizienter Sortieralgorithmus basierend auf Versuch und Irrtum. Bogosort sortiert eine Liste von n Elemente von wiederholt mischen Die Liste, bis sie sich befindet, dass sie sortiert ist. In dem Durchschnitt wird jeder Durchgang durch den Bogosort -Algorithmus einen der der untersucht n! Auftragungen der n Artikel. Wenn die Elemente unterschiedlich sind, wird nur eine solche Bestellung sortiert. Bogosort teilt das Ergleer mit dem Unendlicher Affen Theorem.

Doppelte Exponentialzeit

Ein Algorithmus soll sein Doppelte Exponential Zeit wenn T(n) wird durch 2 Obergrenze begrenzt2Poly (n), wo Poly (n) ist ein Polynom in n. Solche Algorithmen gehören zur Komplexitätsklasse 2-Exptime.

Bekannte Doppel-Exponentialzeitalgorithmen umfassen:

Siehe auch

Verweise

  1. ^ a b Sipser, Michael (2006). Introduction to the Theory of Computation. Kurs Technologie Inc. ISBN 0-619-21764-2.
  2. ^ Mehlhorn, Kurt; Naher, Stefan (1990). "Begrenzte geordnete Wörterbücher in O(Protokollprotokoll N) Zeit und O(n) Platz". Informationsverarbeitungsbriefe. 35 (4): 183–189. doi:10.1016/0020-0190 (90) 90022-P.
  3. ^ Tao, Terence (2010). "1.11 Der ASS -Primalitätstest". Ein Epsilon of Room, II: Seiten aus dem dritten Jahr eines mathematischen Blogs. Graduiertenstudien in Mathematik. Vol. 117. Providence, RI: American Mathematical Society. S. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. HERR 2780010.
  4. ^ Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primalitätstests mit Gaußschen Perioden" (PDF). Zeitschrift der European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/jems/861. HERR 3941463. S2CID 127807021.
  5. ^ a b Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). "BPP verfügt über Simulationen für unterenxponentielle Zeit, es sei denn, die Exptime hat veröffentlichte Beweise". Rechenkomplexität. Berlin, New York: Springer-Verlag. 3 (4): 307–318. doi:10.1007/bf01275486. S2CID 14802332.
  6. ^ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "Effiziente Matrixkette in Polylog -Zeit". Siam Journal über Computing. 27 (2): 466–490. doi:10.1137/s0097539794270698. HERR 1616556.
  7. ^ Holm, Jacob; Rotenberg, Eva (2020). "Volldynamische Planaritätstests in polylogarithmischer Zeit". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (Hrsg.). Verfahren des 52. jährlichen ACM-Sigact-Symposiums für Computertheorie, STOC 2020, Chicago, IL, USA, 22. bis 26. Juni 2020. Verband für Rechenmaschinen. S. 167–180. Arxiv:1911.03449. doi:10.1145/3357713.3384249.
  8. ^ Kumar, Ravi; Rubinfeld, Ronitt (2003). "Sublinear -Zeitalgorithmen" (PDF). Sigact News. 34 (4): 57–67. doi:10.1145/954092.954103. S2CID 65359.
  9. ^ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "Über die Quasilinear-Zeit-Komplexitätstheorie" (PDF). Theoretische Informatik. 148 (2): 325–349. doi:10.1016/0304-3975 (95) 00031-Q. HERR 1355592.
  10. ^ Sedgebick, Robert; Wayne, Kevin (2011). Algorithmen (4. Aufl.). Pearson Ausbildung. p. 186.
  11. ^ Papadimitriou, Christos H. (1994). Rechenkomplexität. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
  12. ^ Cobham, Alan (1965). "Die intrinsische rechnerische Schwierigkeit der Funktionen". Proc. Logik, Methodik und Philosophie der Wissenschaft II.. North Holland.
  13. ^ Grötschel, Martin; László Lovász; Alexander Schrijver (1988). "Komplexität, Orakel und numerische Berechnung". Geometrische Algorithmen und kombinatorische Optimierung. Springer. ISBN 0-387-13624-x.
  14. ^ Schrijver, Alexander (2003). "Vorbereitungen über Algorithmen und Komplexität". Kombinatorische Optimierung: Polyeder und Effizienz. Vol. 1. Springer. ISBN 3-540-44389-4.
  15. ^ Braverman, Mark; Kun-Ko, jung; Rubinstein, Aviad; Weinstein, Omri (2017). "Eth Härte für dichtestek-Subgraph mit perfekter Vollständigkeit ". In Klein, Philip N. (Hrsg.). Verfahren des achtundzwanzigsten jährlichen ACM-SIAM-Symposiums für diskrete Algorithmen, Soda 2017, Barcelona, ​​Spanien, Hotel Porta Fira, 16. bis 19. Januar. Gesellschaft für industrielle und angewandte Mathematik. S. 1326–1341. Arxiv:1504.08352. doi:10.1137/1.9781611974782.86. HERR 3627815.
  16. ^ Komplexitätszoo: Klasse QP: Quasipolynomzeit
  17. ^ a b Impagliazzo, Russell; Paturi, Ramamohan (2001). "Über die Komplexität von k-Sat " (PDF). Journal of Computer and System Sciences. 62 (2): 367–375. doi:10.1006/jcs.2000.1727. HERR 1820597.
  18. ^ Aaronson, Scott (5. April 2009). "Ein nicht ganz exponentielles Dilemma". Shtetl-optimiert. Abgerufen 2. Dezember 2009.
  19. ^ Komplexitätszoo: Klassenunterexp: Deterministische Unterexponentialzeit
  20. ^ Moser, P. (2003). "Baires Kategorien zu kleinen Komplexitätsklassen". In Andrzej Lingas; Bengt J. Nilsson (Hrsg.). Grundlagen der Berechnungstheorie: 14. Internationales Symposium, FCT 2003, Malmö, Schweden, 12.-15. August 2003, Proceedings. Vorlesungsnotizen in Informatik. Vol. 2751. Berlin, New York: Springer-Verlag. S. 333–342. doi:10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.
  21. ^ Miltersen, P.B. (2001). "Derandomisierende Komplexitätsklassen". Handbuch des randomisierten Computers. Kombinatorische Optimierung. Kluwer Academic Pub. 9: 843. doi:10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.
  22. ^ Kuperberg, Greg (2005). "Ein Quantenalgorithmus für das Problem der dihederen versteckten Subgruppenproblem". Siam Journal über Computing. Philadelphia. 35 (1): 188. Arxiv:Quant-Ph/0302112. doi:10.1137/s0097539703436345. ISSN 1095-7111. S2CID 15965140.
  23. ^ ODED Regev (2004). "Ein subexponentieller Zeitalgorithmus für das Problem der polynomialen Untergruppe des dihederen versteckten Untergruppens". Arxiv:Quant-Ph/0406151V1.
  24. ^ Grohe, Martin; Neuen, Daniel (2021). "Jüngste Fortschritte zum Graph -Isomorphismus -Problem". Arxiv:2011.01366. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  25. ^ Flum, Jörg; Grohe, Martin (2006). Parametrisierte Komplexitätstheorie. Springer. p. 417. ISBN 978-3-540-29952-3.
  26. ^ Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "Welche Probleme haben stark exponentielle Komplexität?". Journal of Computer and System Sciences. 63 (4): 512–530. doi:10.1006/jcs.2001.1774.
  27. ^ Mayr, Ernst W.; Meyer, Albert R. (1982). "Die Komplexität der Wortprobleme für kommutative Semigroups und Polynomideale". Fortschritte in der Mathematik. 46 (3): 305–329. doi:10.1016/0001-8708 (82) 90048-2. HERR 0683204.
  28. ^ Davenport, James H.; Heintz, Joos (1988). "Die echte Quantifikator -Eliminierung ist doppelt exponentiell". Zeitschrift für symbolische Berechnung. 5 (1–2): 29–35. doi:10.1016/s0747-7171 (88) 80004-x. HERR 0949111.
  29. ^ Collins, George E. (1975). "Quantifikator -Eliminierung für reale geschlossene Felder durch zylindrische algebraische Zersetzung". In Brakhage, H. (Hrsg.). Automata -Theorie und formale Sprachen: 2. GI -Konferenz, Kaiserslautern, 20. bis 23. Mai 1975. Vorlesungsnotizen in Informatik. Vol. 33. Springer. S. 134–183. doi:10.1007/3-540-07407-4_17. HERR 0403962.