Zeitkomplexität

In der theoretischen Informatik bezeichnet die Zeitkomplexität die Rechenkomplexität , die angibt, wie viel Zeit ein Algorithmus zur Ausführung benötigt. Die Zeitkomplexität wird üblicherweise durch Zählen der vom Algorithmus ausgeführten Elementaroperationen abgeschätzt, wobei angenommen wird, dass jede Elementaroperation eine feste Zeit benötigt. Somit besteht ein konstanter Zusammenhang zwischen der benötigten Zeit und der Anzahl der vom Algorithmus ausgeführten Elementaroperationen .

Da die Laufzeit eines Algorithmus bei Eingaben gleicher Größe variieren kann, betrachtet man üblicherweise die Worst-Case-Zeitkomplexität , also die maximale Laufzeit für Eingaben einer gegebenen Größe. Weniger gebräuchlich und meist explizit angegeben ist die Average-Case-Komplexität , die den Mittelwert der Laufzeit für Eingaben einer gegebenen Größe darstellt (dies ist sinnvoll, da es nur eine endliche Anzahl möglicher Eingaben einer gegebenen Größe gibt). In beiden Fällen wird die Zeitkomplexität im Allgemeinen als Funktion der Eingabegröße ausgedrückt. ^{[ 1 ] : 226} Da diese Funktion im Allgemeinen schwer exakt zu berechnen ist und die Laufzeit für kleine Eingaben meist keine Rolle spielt, konzentriert man sich üblicherweise auf das Verhalten der Komplexität bei zunehmender Eingabegröße – also auf das asymptotische Verhalten der Komplexität. Daher wird die Zeitkomplexität üblicherweise in der O-Notation ausgedrückt , typischerweise O(n ), O( n), O(n ) usw., wobei n die Größe in Bits ist, die zur Darstellung der Eingabe benötigt werden. ${\displaystyle O(n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n^{\alpha })}$${\displaystyle O(2^{n})}$

Die Komplexität von Algorithmen wird anhand der Art der in der O-Notation verwendeten Funktion klassifiziert. Beispielsweise ist ein Algorithmus mit der Zeitkomplexität O(n) ein linearer Algorithmus , und ein Algorithmus mit der Zeitkomplexität O(n) für eine bestimmte Konstante ist ein polynomieller Algorithmus . ${\displaystyle O(n)}$${\displaystyle O(n^{\alpha })}$${\displaystyle \alpha >0}$

Die folgende Tabelle fasst einige Klassen häufig auftretender Zeitkomplexitäten zusammen. In der Tabelle bedeutet poly( x ) = x ^{O (1)} , d.h. Polynom in  x .

Name	Komplexitätsklasse	Zeitkomplexität ( O ( n ) )	Beispiele für Laufzeiten	Beispielalgorithmen
konstante Zeit		${\displaystyle O(1)}$	10	Den Medianwert in einem sortierten Zahlenarray ermitteln . Berechnung von (−1) n .
inverse Ackermann -Zeit		${\displaystyle O{\bigl (}\alpha (n){\bigr )}}$		Amortisierte Zeit pro Operation unter Verwendung eines disjunkten Satzes
iterierte logarithmische Zeit		${\displaystyle O(\log ^{*}n)}$		Verteilte Färbung von Zyklen
log-logarithmisch		${\displaystyle O(\log \log n)}$		Amortisierte Zeit pro Operation unter Verwendung einer Warteschlange mit begrenzter Priorität [ 2 ]
logarithmische Zeit	DLOGTIME	${\displaystyle O(\log n)}$	${\displaystyle \log n}$,${\displaystyle \log(n^{2})}$	Binärsuche
polylogarithmische Zeit		${\displaystyle {\textsf {poly}}(\log n)}$	${\displaystyle (\log n)^{2}}$
Bruchteil		${\displaystyle O(n^{c})}$Wo${\displaystyle 0<c<1}$	${\displaystyle {\sqrt {n}}}$,${\displaystyle n^{\frac {2}{3}}}$	Bereichssuche in einem k -d-Baum
lineare Zeit		${\displaystyle O(n)}$	N ,${\displaystyle 2n+5}$	Das kleinste oder größte Element in einem unsortierten Array finden . Kadanes Algorithmus . Lineare Suche .
"n log-star n" Zeit		${\displaystyle O(n\log ^{*}n)}$		Seidels Polygon -Triangulationsalgorithmus .
linearithmische Zeit		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$,${\displaystyle \log n!}$	Schnellstmögliche Vergleichssortierung . Schnelle Fourier-Transformation .
quasilineare Zeit		${\displaystyle n{\textsf {poly}}(\log n)}$	${\displaystyle n\log ^{2}n}$	Mehrpunkt-Polynomauswertung
quadratische Zeit		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	Bubblesort . Insertionsort . Direkte Faltung .
Kubikzeit		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	Naive Multiplikation zweier Matrizen. Berechnung der partiellen Korrelation . ${\displaystyle n\times n}$
Polynomzeit	P	${\displaystyle 2^{O(\log n)}={\textsf {poly}}(n)}$	${\displaystyle n^{2}+n}$,${\displaystyle n^{10}}$	Karmarkars Algorithmus für lineare Programmierung . AKS-Primzahltest [ 3 ] [ 4 ]
quasi-polynomiale Zeit	QP	${\displaystyle 2^{{\textsf {poly}}(\log n)}}$	${\displaystyle n^{\log \log n}}$,${\displaystyle n^{\log n}}$	Bekanntester O ( log₂n ) -Approximationsalgorithmus für das gerichtete Steinerbaumproblem , bekanntester Paritätsspiellöser [ 5 ] , bekanntester Graphisomorphiealgorithmus
subexponentielle Zeit (erste Definition)	SUBEXP	${\displaystyle O(2^{n^{\epsilon }})}$für alle${\displaystyle \epsilon >0}$		Enthält BPP , es sei denn, EXPTIME (siehe unten) entspricht MA . [ 6 ]
subexponentielle Zeit (zweite Definition)		${\displaystyle 2^{o(n)}}$	${\displaystyle 2^{\sqrt[{3}]{n}}}$	Bester klassischer Algorithmus zur Faktorisierung ganzer Zahlen ehemals bester Algorithmus für Graphisomorphie
exponentielle Zeit (mit linearem Exponenten)	E	${\displaystyle 2^{O(n)}}$	${\displaystyle 1.1^{n}}$,${\displaystyle 10^{n}}$	Lösung des Problems des Handlungsreisenden mithilfe dynamischer Programmierung
Faktorzeit		${\displaystyle O(n)!=2^{O(n\log n)}}$	${\displaystyle n!,n^{n},2^{n\log n}}$	Lösung des Problems des Handlungsreisenden mittels Brute-Force-Suche
exponentielle Zeit	EXPTIME	${\displaystyle 2^{{\textsf {poly}}(n)}}$	${\displaystyle 2^{n}}$,${\displaystyle 2^{n^{2}}}$	Lösung der Matrizenkettenmultiplikation mittels Brute-Force-Suche . Finden einer Gewinnstrategie im Schach , Dame oder Go mit der japanischen Ko-Regel auf einem Brett. ${\displaystyle n\times n}$
doppelt exponentielle Zeit	2-EXPTIME	${\displaystyle 2^{2^{{\textsf {poly}}(n)}}}$	${\displaystyle 2^{2^{n}}}$	Die Wahrheit einer gegebenen Aussage in der Presburger-Arithmetik bestimmen

Ein Algorithmus wird als zeitkonstant (oft einfach als „ Zeit“ dargestellt) bezeichnet, wenn seine Komplexitätsfunktion durch einen Wert beschränkt ist, der sich nicht mit der Größe der Eingabe ändert. Dies bedeutet, dass die Ausführungszeit unabhängig von der verarbeiteten Datenmenge konstant bleibt. Beispielsweise ist der Zugriff auf ein bestimmtes Element in einem Array eine zeitkonstant zeitbasierte Operation, da nur ein einziger Vorgang erforderlich ist, um dieses Element zu finden. ${\textstyle O(1)}$${\textstyle T(n)}$

Im Gegensatz dazu ist die Bestimmung des Minimalwerts in einem unsortierten Array nicht in konstanter Zeit zu bewältigen; sie erfordert die Untersuchung jedes einzelnen Elements , was zu einer linearen Zeitkomplexität von O(n²) führt . Wenn die Anzahl der Elemente jedoch bekannt und festgelegt ist, können bestimmte Aufgaben dennoch als zeitkonstant betrachtet werden. ${\textstyle O(n)}$

Wichtig ist, dass der Begriff „konstante Laufzeit“ nicht bedeutet, dass die Laufzeit völlig unabhängig von der Problemgröße sein muss; vielmehr sollte sie unabhängig von der Eingabegröße eine konsistente Obergrenze aufweisen. Beispielsweise wird eine Aufgabe, bei der die Werte von a und b vertauscht werden , um sicherzustellen, dass eine bestimmte Bedingung erfüllt ist, als konstant zeitlich klassifiziert, selbst wenn die Ausführungszeit je nach Erfüllung dieser Bedingung variieren kann. Entscheidend ist, dass eine Konstante t existiert , sodass die benötigte Zeit unabhängig von den Eingabewerten niemals t überschreitet.${\textstyle a\leq b}$

Algorithmen mit konstanter Laufzeit sind insbesondere in Bereichen wie der Kryptographie von Bedeutung, wo Timing-Angriffe Schwankungen in der Ausführungszeit ausnutzen können. Durch die Entwicklung von Algorithmen mit konstanter Laufzeit können Entwickler die Sicherheit erhöhen und die Vorhersagbarkeit der Leistung gewährleisten. Dies macht die Algorithmen zu einem grundlegenden Aspekt der Softwareentwicklung.

Ein Algorithmus hat eine logarithmische Laufzeit, wenn . Da und durch einen konstanten Multiplikator verknüpft sind und dieser Multiplikator für die Big-O-Klassifizierung irrelevant ist, wird für Algorithmen mit logarithmischer Laufzeit standardmäßig verwendet, unabhängig von der Basis des Logarithmus im Ausdruck für T.${\displaystyle T(n)=O(\log n)}$${\displaystyle \log _{a}n}$${\displaystyle \log _{b}n}$${\displaystyle O(\log n)}$

Algorithmen mit logarithmischer Laufzeit treten häufig bei Operationen auf Binärbäumen oder bei der Verwendung der binären Suche auf .

Ein Algorithmus gilt als hocheffizient, wenn das Verhältnis der Anzahl der Operationen zur Größe der Eingabe mit zunehmendem n sinkt und gegen null strebt . Ein Algorithmus, der auf alle Elemente seiner Eingabe zugreifen muss, kann keine logarithmische Laufzeit haben, da die Zeit zum Einlesen einer Eingabe der Größe n in der Größenordnung von n liegt . ${\displaystyle O(\log n)}$

Ein Beispiel für logarithmische Laufzeit ist die Wörterbuchsuche. Betrachten wir ein Wörterbuch D mit n alphabetisch sortierten Einträgen . Wir nehmen an, dass für alle n ≥ n der k -te Eintrag in konstanter Zeit abgerufen werden kann . Sei w_k dieser k -te Eintrag. Unter diesen Voraussetzungen kann geprüft werden, ob ein Wort w im Wörterbuch enthalten ist, und zwar in logarithmischer Zeit: Wir betrachten w = w_k(n) , wobei w_k die Abrundungsfunktion bezeichnet . Wenn w = 0 – das heißt, das Wort w befindet sich genau in der Mitte des Wörterbuchs –, ist die Suche abgeschlossen. Andernfalls, wenn w < 0 – das heißt, wenn das Wort w alphabetisch vor dem mittleren Wort des gesamten Wörterbuchs steht –, setzen wir die Suche in der linken (also früheren) Hälfte des Wörterbuchs fort und wiederholen dies, bis das gesuchte Wort gefunden ist. Steht es hingegen nach dem mittleren Wort, verfahren wir analog mit der rechten Hälfte des Wörterbuchs. Dieser Algorithmus ähnelt der Methode, die häufig zum Auffinden eines Eintrags in einem gedruckten Wörterbuch verwendet wird. Folglich verringert sich der Suchraum innerhalb des Wörterbuchs, je näher sich der Algorithmus dem Zielwort nähert. ${\displaystyle 1\leq k\leq n}$${\displaystyle D(k)}$${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle \lfloor \;\rfloor }$${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$

Ein Algorithmus hat eine polylogarithmische Laufzeit , wenn seine Laufzeit für eine Konstante k gleich ist . Eine andere Schreibweise dafür ist . ${\displaystyle T(n)}$${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$${\displaystyle O(\log ^{k}n)}$

Beispielsweise kann die Ordnung von Matrixketten auf einer parallelen Random-Access-Maschine in polylogarithmischer Zeit gelöst werden ^{[ 7 ]} , und die Planarität eines Graphen kann vollständig dynamisch in der Zeit pro Einfüge-/Löschoperation bestimmt werden ^{[ 8 ] .}${\displaystyle O(\log ^{3}n)}$

Ein Algorithmus läuft in sublinearer Zeit (oft auch als sublineare Zeit bezeichnet ), wenn . Dies schließt insbesondere Algorithmen mit den oben definierten Zeitkomplexitäten ein. ${\displaystyle T(n)=o(n)}$

Der Begriff „sublinearer Zeitalgorithmus“ bezeichnet üblicherweise randomisierte Algorithmen, die einen kleinen Teil ihrer Eingaben als Stichprobe verwenden und diese effizient verarbeiten, um näherungsweise Eigenschaften der gesamten Instanz abzuleiten. ^{[ 9 ]} Diese Art von sublinearem Zeitalgorithmus ist eng mit Eigenschaftstests und Statistik verwandt .

Weitere Anwendungsfälle, in denen Algorithmen in sublinearer Zeit ausgeführt werden können, sind:

• Parallele Algorithmen mit linearem oder größerem Gesamtaufwand ( wodurch sie die gesamte Eingabe lesen können), aber sublinearer Tiefe .
• Algorithmen, die garantierte Annahmen über die Eingabestruktur treffen. Ein wichtiges Beispiel sind Operationen auf Datenstrukturen , z. B. die binäre Suche in einem sortierten Array.
• Algorithmen, die nach lokalen Strukturen in der Eingabe suchen, beispielsweise nach einem lokalen Minimum in einem eindimensionalen Array (was  mit einer Variante der binären Suche in O(n²) Zeit gelöst werden kann), sind eng mit dem Konzept der lokalen Berechnungsalgorithmen (LCA) verbunden. Hierbei erhält der Algorithmus eine große Eingabe und fragt lokale Informationen über eine gültige große Ausgabe ab. ^{[ 10 ]}${\displaystyle O(\log(n))}$

Ein Algorithmus hat eine lineare Laufzeit (oder O(n)), wenn seine Zeitkomplexität O(n) beträgt . Anschaulich bedeutet dies, dass die Laufzeit höchstens linear mit der Größe der Eingabe ansteigt. Genauer gesagt bedeutet dies, dass es eine Konstante c gibt , sodass die Laufzeit für jede Eingabe der Größe n höchstens O(n) beträgt . Beispielsweise benötigt eine Prozedur, die alle Elemente einer Liste addiert, eine Laufzeit proportional zur Länge der Liste, wenn die Additionszeit konstant oder zumindest durch eine Konstante beschränkt ist. ${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle cn}$

Lineare Laufzeit ist die bestmögliche Zeitkomplexität, wenn ein Algorithmus seine gesamte Eingabe sequenziell einlesen muss. Daher wurde viel Forschung in die Entwicklung von Algorithmen mit linearer oder zumindest nahezu linearer Laufzeit investiert. Diese Forschung umfasst sowohl Software- als auch Hardwaremethoden. Verschiedene Hardwaretechnologien nutzen Parallelverarbeitung , um dies zu ermöglichen. Ein Beispiel hierfür ist inhaltsadressierbarer Speicher (CAM ). Dieses Konzept der linearen Laufzeit findet Anwendung in String-Matching-Algorithmen wie dem Boyer-Moore-Algorithmus und dem Ukkonen-Algorithmus .

Ein Algorithmus läuft in quasilinearer Zeit (auch als log-lineare Zeit bezeichnet ), wenn für eine positive Konstante k gilt ; ^{[ 11 ]} linearithmische Zeit ist der Fall . ^{[ 12 ]} In der Soft-O-Notation sind diese Algorithmen gegeben durch . Quasilineare Zeitalgorithmen sind auch für jede Konstante gegeben und laufen daher schneller als jeder Polynomzeitalgorithmus, dessen Zeitschranke einen Term für jedes enthält . ${\displaystyle T(n)=O(n\log ^{k}n)}$${\displaystyle k=1}$${\displaystyle {\tilde {O}}(n)}$${\displaystyle O(n^{1+\varepsilon })}$${\displaystyle \varepsilon >0}$${\displaystyle n^{c}}$${\displaystyle c>1}$

Zu den Algorithmen, die in quasilinearer Zeit laufen, gehören:

• In-Place-Merge-Sortierung ,${\displaystyle O(n\log ^{2}n)}$
• Quicksort hat in seiner randomisierten Version eine Laufzeit, die der erwarteten Laufzeit im ungünstigsten Fall entspricht. Die nicht-randomisierte Version hat eine Laufzeit, die nur bei Betrachtung der durchschnittlichen Komplexität berechnet wird .${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$
• Heapsort , Mergesort , Introsort , Binärbaumsort, Smoothsort , Patience Sort usw. im schlimmsten Fall${\displaystyle O(n\log n)}$
• Schnelle Fourier-Transformationen ,${\displaystyle O(n\log n)}$
• Monge-Array -Berechnung,${\displaystyle O(n\log n)}$
• Schönhage-Strassen-Algorithmus zur Multiplikation ,${\displaystyle O(n\log n\log \log n)}$

In vielen Fällen entspricht die Laufzeit einfach der n -fachen Ausführung einer Operation (zur Notation siehe Big-O-Notation § Familie der Bachmann-Landau-Notationen ). Beispielsweise erzeugt der Binärbaumsortieralgorithmus einen Binärbaum , indem er jedes Element des n -gliedrigen Arrays nacheinander einfügt. Da die Einfügeoperation in einem selbstbalancierenden Binärbaum O( n) benötigt , hat der gesamte Algorithmus O(n²) Zeit. ${\displaystyle O(n\log n)}$${\displaystyle \Theta (\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

Vergleichssortierverfahren benötigen im schlimmsten Fall mindestens Vergleiche , da nach der Stirling-Approximation gilt . Sie entstehen auch häufig aus der Rekursionsformel . ${\displaystyle \Omega (n\log n)}$${\displaystyle \log(n!)=\Theta (n\log n)}$${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

Ein Algorithmus heißt subquadratisch, wenn . ${\displaystyle T(n)=o(n^{2})}$

Beispielsweise haben einfache, vergleichsbasierte Sortieralgorithmen eine quadratische Laufzeit (z. B. Insertion Sort ), während fortgeschrittenere Algorithmen subquadratisch sind (z. B. Shell Sort ). Kein universeller Sortieralgorithmus hat eine lineare Laufzeit, aber der Übergang von quadratischer zu subquadratischer Laufzeit ist von großer praktischer Bedeutung.

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(n^k) for some positive constant k.^[1][13]Problems for which a deterministic polynomial-time algorithm exists belong to the complexity classP, which is central in the field of computational complexity theory. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".^[14]

Some examples of polynomial-time algorithms:

• The selection sort sorting algorithm on n integers performs ${\displaystyle An^{2}}$ operations for some constant A. Thus it runs in time ${\displaystyle O(n^{2})}$ and is a polynomial-time algorithm.
• All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
• Maximum matchings in graphs can be found in polynomial time. In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms.

These two concepts are only relevant if the inputs to the algorithms consist of integers.

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

• P: The complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time
• NP: The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time
• ZPP: The complexity class of decision problems that can be solved with zero error on a probabilistic Turing machine in polynomial time
• RP: The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
• BPP: The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time
• BQP : Die Komplexitätsklasse der Entscheidungsprobleme, die mit einem zweiseitigen Fehler auf einer Quanten-Turingmaschine in Polynomialzeit

P ist die kleinste Zeitkomplexitätsklasse auf einer deterministischen Maschine, die gegenüber Änderungen des Maschinenmodells robust ist . (Beispielsweise kann der Wechsel von einer Einband-Turingmaschine zu einer Mehrbandmaschine zu einer quadratischen Beschleunigung führen, aber jeder Algorithmus, der unter einem Modell in Polynomialzeit läuft, tut dies auch unter dem anderen.) Jede abstrakte Maschine besitzt eine Komplexitätsklasse, die den Problemen entspricht, die auf dieser Maschine in Polynomialzeit gelöst werden können.

Ein Algorithmus hat eine superpolynomielle Laufzeit , wenn T ( n ) nicht durch ein Polynom nach oben beschränkt ist; das heißt, wenn ⁠ ⁠${\displaystyle T(n)\not \in O(n^{c})}$ für jede positive ganze Zahl c gilt .

Ein Algorithmus, der beispielsweise 2 ⁿ Schritte lang auf einer Eingabe der Größe n ausgeführt wird , benötigt superpolynomielle Zeit (genauer: exponentielle Zeit).

Ein Algorithmus mit exponentiellem Ressourcenverbrauch ist offensichtlich superpolynomiell, manche Algorithmen hingegen nur schwach superpolynomiell. Beispielsweise benötigt der Adleman-Pomerance-Rumely-Primzahltest für n- Bit-Eingaben eine Laufzeit von n ^{O (log log n ) . Diese Laufzeit wächst für ausreichend große} n schneller als die jedes Polynoms , doch die Eingabegröße muss unpraktisch groß werden, bevor sie nicht mehr von einem Polynom kleinen Grades dominiert werden kann.

Ein Algorithmus mit superpolynomieller Laufzeit liegt außerhalb der Komplexitätsklasse P. Cobhams These besagt , dass solche Algorithmen unpraktisch sind, und in vielen Fällen trifft dies zu. Da das P-vs.-NP-Problem ungelöst ist, ist unbekannt, ob NP-vollständige Probleme superpolynomielle Laufzeit benötigen.

Quasi-polynomiale Algorithmen sind Algorithmen, deren Laufzeit quasi-polynomiales Wachstum aufweist . Dieses Verhalten ist zwar langsamer als polynomiale Laufzeit, aber deutlich schneller als exponentielle Laufzeit . Die Laufzeit im schlechtesten Fall eines quasi-polynomialen Algorithmus beträgt für ein festes n ≥ 0. Für n ≥ 0 ergibt sich polynomiale Laufzeit, für n ≥ 0 sublineare Laufzeit. ${\displaystyle 2^{O(\log ^{c}n)}}$${\displaystyle c>0}$${\displaystyle c=1}$${\displaystyle c<1}$

Es gibt Probleme, für die wir quasi-polynomiale Algorithmen kennen, aber keine polynomialen Algorithmen. Solche Probleme treten bei Approximationsalgorithmen auf; ein bekanntes Beispiel ist das Problem des gerichteten Steinerbaums , für das ein quasi-polynomialer Approximationsalgorithmus mit einem Approximationsfaktor von O ( n ) (wobei n die Anzahl der Knoten ist) existiert. Der Nachweis der Existenz eines solchen polynomialen Algorithmus ist jedoch ein offenes Problem. ${\displaystyle O(\log ^{3}n)}$

Zu den anderen Rechenproblemen mit quasi-polynomiellen Lösungen, aber ohne bekannte polynomielle Lösung, gehört das Problem der eingepflanzten Clique, bei dem es darum geht, eine große Clique in der Vereinigung einer Clique und eines Zufallsgraphen zu finden . Obwohl es quasi-polynomiell lösbar ist, wurde vermutet, dass das Problem der eingepflanzten Clique keine polynomielle Lösung besitzt. Diese Vermutung wurde als Annahme über die Rechenschwierigkeit verwendet , um die Schwierigkeit verschiedener anderer Probleme in der algorithmischen Spieltheorie , im Eigenschaftstest und im maschinellen Lernen zu beweisen . ^{[ 15 ]}

Die Komplexitätsklasse QP umfasst alle Probleme, für die es Algorithmen mit quasi-polynomieller Laufzeit gibt. Sie kann wie folgt in Bezug auf DTIME definiert werden . ^{[ 16 ]}

${\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}$

In der Komplexitätstheorie stellt das ungelöste P-versus-NP- Problem die Frage, ob alle Probleme in NP polynomiale Algorithmen besitzen. Alle bekannten Algorithmen für NP-vollständige Probleme wie 3SAT usw. benötigen exponentielle Zeit. Tatsächlich wird für viele natürliche NP-vollständige Probleme vermutet, dass sie keine subexponentiellen Algorithmen besitzen. „Subexponentielle Zeit“ ist hier im Sinne der zweiten unten dargestellten Definition zu verstehen. (Andererseits sind viele Graphprobleme, die auf natürliche Weise durch Adjazenzmatrizen dargestellt werden, in subexponentieller Zeit lösbar, einfach weil die Größe der Eingabe dem Quadrat der Anzahl der Knoten entspricht.) Diese Vermutung (für das k-SAT-Problem) ist als Exponentialzeithypothese bekannt . ^{[ 17 ]} Da vermutet wird, dass NP-vollständige Probleme keine quasi-polynomiellen Algorithmen besitzen, basieren einige Unapproximierbarkeitsresultate im Bereich der Approximationsalgorithmen auf dieser Annahme. Siehe beispielsweise die bekannten Unapproximierbarkeitsresultate für das Mengenüberdeckungsproblem .

Der Begriff „subexponentielle Laufzeit“ beschreibt eine Situation, in der die Laufzeit eines Algorithmus zwar schneller wächst als jedes Polynom, aber dennoch deutlich kürzer als eine Exponentialfunktion ist. In diesem Sinne sind Probleme mit subexponentiellen Algorithmen etwas leichter zu handhaben als solche mit ausschließlich exponentiellen Algorithmen. Die genaue Definition von „subexponentiell“ ist nicht allgemein anerkannt ^{[ 18 ]} , die beiden gebräuchlichsten Definitionen sind jedoch im Folgenden aufgeführt.

Ein Problem heißt subexponentiell lösbar, wenn es in Laufzeiten gelöst werden kann, deren Logarithmen kleiner werden als jedes beliebige Polynom. Genauer gesagt, ist ein Problem subexponentiell lösbar, wenn für jedes ε > 0 ein Algorithmus existiert, der das Problem in der Zeit O (2 ^{^ nε} ) löst. Die Menge aller solcher Probleme bildet die Komplexitätsklasse SUBEXP , die sich wie folgt mithilfe von DTIME definieren lässt . ^{[ 6 ] [ 19 ] [ 20 ] [ 21 ]}

${\displaystyle {\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)}$

Dieser Begriff der Subexponentialfunktion ist in Bezug auf ε nicht einheitlich, da ε nicht Teil der Eingabe ist und jedes ε seinen eigenen Algorithmus für das Problem haben kann.

Einige Autoren definieren subexponentielle Laufzeit als Laufzeiten in . ^{[ 17 ] [ 22 ] [ 23 ]} Diese Definition erlaubt größere Laufzeiten als die erste Definition subexponentieller Laufzeit. Ein Beispiel für einen solchen subexponentiellen Algorithmus ist der bekannteste klassische Algorithmus zur Faktorisierung ganzer Zahlen, das allgemeine Zahlkörpersieb , das in etwa in läuft , wobei die Länge der Eingabe n ist . Ein weiteres Beispiel war das Graphisomorphieproblem , das der beste bekannte Algorithmus von 1982 bis 2016 in löste . Auf der STOC 2016 wurde jedoch ein quasi-polynomialer Algorithmus vorgestellt. ^{[ 24 ]}${\displaystyle 2^{o(n)}}$${\displaystyle 2^{{O}(n^{1/3}(\log n)^{2/3})}}$${\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}$

Es macht einen Unterschied, ob der Algorithmus subexponentiell in der Größe der Instanz, der Anzahl der Knoten oder der Anzahl der Kanten sein darf. In der parametrisierten Komplexität wird dieser Unterschied explizit durch die Betrachtung von Paaren aus Entscheidungsproblemen und Parametern k verdeutlicht . SUBEPT ist die Klasse aller parametrisierten Probleme, die in subexponentieller Zeit in k und polynomiell in der Eingabegröße n laufen : ^{[ 25 ]}${\displaystyle (L,k)}$

${\displaystyle {\textsf {SUBEPT}}={\textsf {DTIME}}\left(2^{o(k)}\cdot {\textsf {poly}}(n)\right).}$

Genauer gesagt ist SUBEPT die Klasse aller parametrisierten Probleme, für die es eine berechenbare Funktion mit und einen Algorithmus gibt, der L in der Zeit entscheidet . ${\displaystyle (L,k)}$${\displaystyle f:\mathbb {N} \to \mathbb {N} }$${\displaystyle f\in o(k)}$${\displaystyle 2^{f(k)}\cdot {\textsf {poly}}(n)}$

Die Hypothese der exponentiellen Laufzeit ( ETH ) besagt, dass das Erfüllbarkeitsproblem 3SAT für Boolesche Formeln in konjunktiver Normalform mit höchstens drei Literalen pro Klausel und n Variablen nicht in 2 ^{^o ( n )} Zeit gelöst werden kann . Genauer gesagt besagt die Hypothese, dass es eine absolute Konstante c > 0 gibt , sodass 3SAT von keiner deterministischen Turingmaschine in 2 ^{^cn} Zeit entschieden werden kann. Bezeichnet m die Anzahl der Klauseln, ist ETH äquivalent zur Hypothese, dass kSAT für keine ganze Zahl k ≥ 3 in 2^{^o ( m )} Zeit gelöst werden kann . ^{[ 26 ]} Die Hypothese der exponentiellen Laufzeit impliziert P ≠ NP .

Ein Algorithmus heißt exponentiell , wenn T ( n ) durch 2 ^{^{poly( n )}} nach oben beschränkt ist , wobei poly( n ) ein Polynom in n ist . Formaler ausgedrückt: Ein Algorithmus ist exponentiell, wenn T ( n ) durch O (2 ^{^nk} ) für eine Konstante k beschränkt ist . Probleme, die auf einer deterministischen Turingmaschine exponentielle Algorithmen zulassen, bilden die Komplexitätsklasse EXP .

${\displaystyle {\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)}$

Manchmal wird der Begriff „exponentielle Zeit“ für Algorithmen verwendet, deren Laufzeit T ( n ) = 2^{^{O ( n )}} ist , wobei der Exponent höchstens eine lineare Funktion von n ist . Dies führt zur Komplexitätsklasse E.

${\displaystyle {\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)}$

Ein Algorithmus heißt faktorielle Zeit , wenn T(n) durch die Fakultätsfunktion n! nach oben beschränkt ist . Faktorielle Zeit ist eine Teilmenge der Exponentialzeit (EXP), da für alle n ≥ n gilt: T(n ) ≤ n!. Sie ist jedoch keine Teilmenge von E. ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$${\displaystyle \epsilon >0}$

Ein Beispiel für einen Algorithmus mit Fakultätszeit ist Bogosort , ein notorisch ineffizienter Sortieralgorithmus, der auf dem Prinzip von Versuch und Irrtum basiert . Bogosort sortiert eine Liste von n Elementen, indem die Liste so lange wiederholt gemischt wird , bis sie sortiert ist. Im Durchschnitt untersucht jeder Durchlauf des Bogosort-Algorithmus eine der n ! möglichen Anordnungen der n Elemente. Sind die Elemente verschieden, ist nur eine dieser Anordnungen sortiert. Bogosort ist verwandt mit dem Satz vom unendlichen Affen .

Ein Algorithmus heißt doppelt exponentiell , wenn T ( n ) nach oben durch 2 ^{^2 poly( n )} beschränkt ist , wobei poly( n ) ein Polynom in n ist . Solche Algorithmen gehören zur Komplexitätsklasse 2-EXPTIME .

${\displaystyle {\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)}$

Zu den bekannten Algorithmen mit doppelt exponentieller Laufzeit gehören:

• Entscheidungsverfahren für die Presburger-Arithmetik
• Berechnung einer Gröbner-Basis (im ungünstigsten Fall ^{[ 27 ]} )
• Die Quantorenelimination auf reellen abgeschlossenen Körpern benötigt mindestens doppelt exponentielle Zeit ^{[ 28 ]} und kann in dieser Zeit durchgeführt werden. ^{[ 29 ]}

• L-Notation
• Raumkomplexität