Časová složitost algoritmu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. června 2022; kontroly vyžadují 3 úpravy .

V informatice je časová složitost algoritmu definována jako funkce délky řetězce reprezentujícího vstup, rovné době běhu algoritmu na daném vstupu [1] . Časová složitost algoritmu se obvykle vyjadřuje pomocí velkého zápisu "O" , který bere v úvahu pouze člen nejvyššího řádu a také nebere v úvahu konstantní faktory, tedy koeficienty. Je-li složitost vyjádřena tímto způsobem, hovoříme o asymptotickém popisu časové složitosti, to znamená, že velikost vstupu má tendenci k nekonečnu. Například, pokud existuje takové číslo , že doba běhu algoritmu pro všechny vstupy délky nepřesáhne , pak lze časovou složitost tohoto algoritmu asymptoticky odhadnout jako . $n_{0}$ $n>n_{0}$ $5n^{3}+3n$ $O(n^{3})$

Časová složitost se obvykle odhaduje spočtením počtu elementárních operací, které algoritmus provede. Doba provádění jedné takové operace se bere jako konstanta, to znamená, že se asymptoticky odhaduje jako . V takovém zápisu se celková doba provádění a počet elementárních operací provedených algoritmem liší maximálně o konstantní faktor, který se v O-notaci nezohledňuje. Protože se doba běhu algoritmu může lišit na vstupech stejné velikosti, obvykle se používá nejhorší případ běhu , který se označuje a je definován jako nejdelší doba běhu algoritmu na všech vstupních délkách . Méně často, a to je obvykle specifikováno specificky, se počítá průměrná složitost , tedy matematické očekávání doby běhu pro všechny možné vstupy. Doba běhu algoritmu může být klasifikována podle toho, která funkce je pod O-notací. Například algoritmus s se nazývá algoritmus s lineární dobou běhu a algoritmus s pro některé se nazývá polynom . $O(1)$ $T(n)$ $n$ $T(n)\in O(n)$ $T(n)\in O(n^{\alpha })$ $\alpha >1$

Rozvrh obtížnosti

Následující tabulka shrnuje nejčastěji se vyskytující třídy složitosti . V tabulce , označuje libovolný polynom v , to je, . $poly(x)$ $X$ ${\displaystyle poly(x)=x^{O(1)))$

název	Třída obtížnosti	Pracovní doba, $T(n)$	Příklady pracovní doby	Příklady algoritmů
konstantní čas		$O(1)$	$deset$	Určení parity celého čísla (reprezentovaného binárně)
inverzní Ackermannova funkce		$O(\alpha (n))$		Analýza amortizace na operaci pomocí disjunktních sad
iterovaný logaritmický čas		$O(\log ^{*}n)$		Barvy v distribuovaném cyklu
dvojitě logaritmické		$O(\log \log n)$		Doba amortizace na operaci při použití fronty s omezenou prioritou [2]
logaritmický čas	DLOGTIME	$O(\log n)$	$\log n$ , $\log n^{2}$	Binární vyhledávání
polylogaritmický čas		$poly(\log n)$	$(\log n)^{2}$
sublineární čas		$O(n^{c})$ v $0<c<1$	$n^{1/2}$ , $n^{2/3}$	Hledejte v k-rozměrném stromu
lineární čas		$Na)$	$n$	Hledání nejmenšího nebo největšího prvku v netříděném poli
"n log-hvězdička n"		$O(n\log ^{*}n)$		Seidelův polygonový triangulační algoritmus .
lineárně-logaritmický čas		$O(n\log n)$	$n\log n$ , $\log n!$	Nejrychlejší srovnávací řazení
kvadratický čas		$O(n^{2})$	$n^{2}$	Bublinové řazení , řazení vkládání , přímé skládání
krychlový čas		$O(n^{3})$	$n^3$	Obvyklé násobení dvou matic. Výpočet parciální korelace . $n\krát n$
polynomiální čas	P	$2^{O(\log n)}=poly(n)$	$n$ .. _ $n\log n$ ${\displaystyle n^{10))$	Karmarkarův algoritmus pro lineární programování , AKS-test jednoduchosti
kvazi-polynomiální čas	QP	${\displaystyle 2^{poly(\log n)))$	${\displaystyle n^{\log \log n))$ , ${\displaystyle n^{\log n))$	Nejrychlejší známý je aproximační algoritmus pro orientovaný Steinerův problém . $O(\log ^{2}n)$
subexponenciální čas (první definice)	SUBEXP	$O(2^{n^{\varepsilon )))$ pro všechny $\varepsilon >0$	$2^{\log n^{\log \log n))$	Za předpokladu teoretických hypotéz je BPP obsažen v SUBEXP. [3]
subexponenciální čas (druhá definice)		$2^{o(n)}$	$2^{n^{1/3}}$	Nejrychlejší známé algoritmy pro faktoring celých čísel a kontrolu izomorfismu grafu
exponenciální čas (s lineárním exponentem)	E	$2^{O(n)}$	$1.1^{n}$ , $10^{n}$	Řešení problému obchodního cestujícího s dynamickým programováním
exponenciální čas	EXPTIME	${\displaystyle 2^{poly(n)))$	$2^{{n}}$ , $2^{n^{2))$	Řešení problému řádu násobení matic pomocí vyčerpávajícího výčtu
faktoriální čas		$O(n!)$	$n$	Řešení problému obchodního cestujícího vyčerpávajícím hledáním
dvojnásobně exponenciální čas	2-EXPTIME	$2^{2^{poly(n)))$	$2^{{2^{n}}}$	Kontrola správnosti daného tvrzení v Presburgerově aritmetice
		${\sqrt[{n}]{\log _{n}(n)))$	1 pro n >= 1

Konstantní čas

O algoritmu se říká, že je to algoritmus s konstantním časem (zapsaný jako time ), pokud je hodnota omezena na hodnotu nezávislou na velikosti vstupu. Například získání jednoho prvku v poli trvá konstantní čas, protože je proveden jediný příkaz k jeho nalezení. Nalezení minimální hodnoty v netříděném poli však není operace s konstantním časem, protože se musíme podívat na každý prvek pole. Tato operace tedy trvá lineárně, . Pokud je počet prvků znám předem a nemění se, lze takový algoritmus označit jako algoritmus s konstantním časem. $O(1)$ $T(n)$ $Na)$

Navzdory názvu „konstantní čas“ nemusí být doba běhu nezávislá na velikosti úlohy, ale horní mez doby běhu by měla být. Například problém „výměny hodnot a v případě potřeby získat výsledek “ je považován za problém s konstantním časem, ačkoli doba běhu algoritmu může záviset na tom, zda nerovnost již platí nebo ne. Existuje však určitá konstanta, u které doba provedení úlohy nikdy nepřekročí . $A$ $b$ $a\leq b$ $a\leq b$ $t$ $t$

Níže je uveden příklad kódu běžícího v konstantním čase:

int index = 5; int položka = seznam[index]; jestliže (podmínka je pravdivá) pak provádět některé operace s konstantní dobou běhu jiný provádět některé operace s konstantní dobou běhu pro i = 1 až 100 pro j = 1 až 200 provádět některé operace s konstantní dobou běhu

Pokud je rovno , kde je konstanta, pak je toto ekvivalentní rovno . $T(n)$ $O(\alpha )$ $\alpha$ $T(n)$ $O(1)$

Logaritmický čas

Říká se, že algoritmus běží v logaritmickém čase , pokud . Protože počítače používají binární číselný systém , základem logaritmu je (tj. ). Při změně základu logaritmu se však liší pouze konstantním faktorem , který je v O-big notaci vyřazen. Jedná se tedy o standardní zápis pro logaritmické časové algoritmy bez ohledu na základ logaritmu. $T(n)=O(\log n)$ $2$ $\log _{2}n$ $\log _{a}n$ $\log _{b}n$ $\log_b a$ $O(\log n)$

Algoritmy běžící v logaritmickém čase se běžně vyskytují v operacích na binárních stromech nebo při použití binárního vyhledávání .

$O(\log n)$ Algoritmy pro práci s poli velikostí dat jsou považovány za vysoce efektivní, protože poměr doby provádění jedné operace k velikosti pole se zvětšováním této velikosti klesá. $n$

Velmi jednoduchým příkladem takového algoritmu je vyhledávání slov ve slovníku. Představte si slovník obsahující slova seřazená abecedně. Zároveň předpokládáme, že všechna slova mají délku a že můžeme přistupovat k libovolnému prvku slovníku indexem v konstantním čase. Nechť je -tý prvek slovníku, pak můžete zkontrolovat, zda je slovo ve slovníku za . Chcete-li to provést, zvažte prvek slovníku , kde označuje zaokrouhlení čísla dolů . Pokud , pak bychom měli jít do pravé poloviny pole, jinak - doleva. Na konci dostaneme index prvního slova, který je roven nebo lexikograficky větší než . $D$ $n$ $O(1)$ $D(k)$ $k$ $\omega$ $O(\log n)$ $D(\lfloor n/2\rfloor )$ $\lfloor ~\rfloor$ $D(\lfloor n/2\rfloor )<\omega$ $\omega$

int find ( vector < string > & D , string w ) { int n = D . velikost (); int l = -1 , r = n ; while ( r - l > 1 ) { int m = ( l + r ) / 2 ; if ( D [ m ] < w ) { l = m ; } jinak { r = m ; } } vrátit r ; }

Polylogaritmický čas

Říká se, že algoritmus běží v polylogaritmickém čase , pokud pro některé . Například problém řádu násobení matic lze v takovém čase vyřešit na paralelním stroji RAM [4] . $T(n)=O(\log ^{k}n)$ $k$

Sublineární čas

Říká se, že algoritmus běží v sublineárním čase , pokud . Konkrétně sem patří algoritmy, jejichž časová složitost je výše uvedená, stejně jako například Groverovo hledání se složitostí . $T(n)=o(n)$ $O(n^{{1/}})$

Algoritmy, které jsou sice přesné, ale stále běží v sublineárním čase, obvykle používají paralelismus procesů (stejně jako algoritmus výpočtu determinant matice NC 1 ), neklasické výpočty (jako v Groverově hledání) nebo mají zaručený odhad vstupní struktury (jako binární vyhledávací algoritmy a mnoho algoritmů pro zpracování stromů). Nicméně formální jazyky , jako je jazyk slov, která mají 1 bit na pozici určené prvními bity slova, mohou být rozhoditelné v sublineárním čase, i když jakýkoli bit může být důležitý pro určení, zda slovo patří do jazyka. . $\log n$

Termín sublineární algoritmus doby běhu se obvykle používá pro algoritmy, které na rozdíl od příkladů výše běží na konvenčních sekvenčních modelech strojů a nevyžadují a priori znalost vstupní struktury [5] . Mohou však používat pravděpodobnostní metody a ještě více, často musí být randomizováni pro jakýkoli netriviální úkol.

Protože takový algoritmus musí dát odpověď bez úplného čtení vstupních dat, je velmi závislý na přístupových metodách povolených ve vstupním toku. Obvykle se pro tok, který je bitovým řetězcem , předpokládá, že algoritmus může požadovat hodnotu pro libovolný . ${\displaystyle b_{1},\tečky ,b_{k))$ $O(1)$ $bi}$ $i$

Algoritmy sublineárního času jsou obvykle pravděpodobnostní a poskytují pouze přibližné řešení. Sublineární runtime algoritmy přirozeně vznikají při zkoumání kontroly vlastností .

Lineární čas

Říká se, že algoritmus běží v lineárním čase nebo v čase, pokud je jeho složitost . Neformálně to znamená, že pro dostatečně velkou velikost vstupu se doba běhu lineárně zvyšuje s velikostí vstupu. Například procedura, která sečte všechny prvky seznamu, trvá úměrně délce seznamu. Tento popis není zcela přesný, protože doba běhu se může výrazně lišit od přesné úměrnosti, zejména u malých hodnot . $Na)$ $Na)$ $n$

Lineární čas je často považován za žádoucí atribut algoritmu [6] . Bylo provedeno mnoho výzkumů pro vytvoření algoritmů s (téměř) lineárními nebo lepšími provozními dobami. Tyto studie zahrnovaly jak softwarové, tak hardwarové přístupy. V případě hardwarového provádění mohou některé algoritmy, které z matematického hlediska nikdy nemohou dosáhnout lineárního času provádění ve standardních výpočetních modelech , běžet v lineárním čase. Existují některé hardwarové technologie, které k dosažení tohoto cíle využívají paralelismus . Příkladem je asociativní paměť . Tento koncept lineárního času se používá v problémech se vzorem , jako je Boyer-Mooreův algoritmus a Ukkonenův algoritmus .

Kvazilineární čas

Říká se, že algoritmus běží v kvazilineárním čase, pokud pro nějakou konstantu . Když se mluví o lineárně-logaritmickém čase [7] . Z hlediska soft-O se taková doba běhu zapisuje jako . U algoritmů s kvazilineární dobou běhu platí také odhad pro libovolný . Tyto algoritmy jsou tedy rychlejší než jakýkoli polynom v , jehož stupeň je větší než . $T(n)=O(n\log ^{k}n)$ $k$ $k=1$ ${\tilde {O}} (n)$ $T(n)\in o(n^{1+\varepsilon })$ $\varepsilon >0$ $n$ $jeden$

Algoritmy běžící v kvazilineárním čase, kromě lineárně-logaritmických algoritmů uvedených výše, zahrnují:

Sloučení na místě řazení : ; $O(n\log ^{2}n)$
Rychlé řazení : matematické očekávání doby běhu pravděpodobnostní verze algoritmu spočívá v libovolném vstupu, u deterministické verze je tento odhad správný pouze v průměru přes všechny vstupy; $O(n\log n)$
Hromadné třídění , slučovací třídění , introsort , binární strom sort , plynulé třídění , solitaire sort další: nejhorší případ; $O(n\log n)$
Rychlá Fourierova transformace : ; $O(n\log n)$
Algoritmy na Mongeových maticích : . $O(n\log n)$

Lineárně-logaritmický čas

Lineární-logaritmický je speciální případ kvazi-lineárního času s exponentem na logaritmickém faktoru. $k=1$

Lineárně-logaritmická funkce je funkcí formy (tj. součin lineárního a logaritmického členu). Říká se, že algoritmus běží v lineárně-logaritmickém čase , jestliže [8] . Lineárně-logaritmická funkce tedy roste rychleji než lineární, ale pomaleji než jakýkoli polynom stupně většího než . $n\log n$ $T(n)=O(n\log n)$ $n$ $jeden$

V mnoha případech je doba běhu jednoduše výsledkem provedení časové operace na době běhu . Například řazení pomocí binárního stromu vytvoří binární strom tak, že do něj vložíte každý prvek pole velikosti jeden po druhém. Protože operace vložení do vyváženého binárního vyhledávacího stromu zabere čas , bude celková doba provádění algoritmu lineárně-logaritmická. $n\log n$ $n$ $O(\log n)$ $n$ $O(\log n)$

Jakékoli třídění založené na porovnání vyžaduje alespoň nejhorší případ lineárně-logaritmického počtu srovnání. Jedno z jednoduchých zdůvodnění této skutečnosti z informačně-teoretického hlediska vypadá takto: v důsledku řazení dostaneme permutaci délky , která jednoznačně určuje pořadí prvků. Celkem existují různá řazení, pokud chceme každé z nich jednoznačně zakódovat nějakou posloupností bitů, budeme potřebovat v průměru ne méně než bitů informace na permutaci. V tomto případě je výsledkem párového porovnání dvou prvků pole právě jeden bit informace – buď je první prvek menší než druhý, nebo ne. Pokud tedy pro třídění použijeme pouze párová srovnání, není možné seřadit pole v lepším než nejhorším případě. Zároveň takový odhad pro mnoho rekurzivních druhů, jako je merge sort , často vychází z rekurzivní rovnice . $n$ $n$ $\log n!\sim n\log n$ $O(n\log n)$ $T(n)=T(n/2)+O(n)$

Podčtvercový čas

Říká se, že algoritmus běží v subkvadratickém čase , pokud . $T(n)=o(n^{2})$

Například jednoduché třídicí algoritmy založené na porovnání (jako je vložení řazení ) jsou kvadratické. Současně lze nalézt pokročilejší algoritmy, které mají subkvadratické běhové prostředí (např. Shell sort ). Žádné obecné druhy nefungují v lineárním čase, ale přechod z kvadratického na podkvadrátový čas má velký praktický význam.

Polynomiální čas

Říká se, že algoritmus běží v polynomiálním čase , pokud je doba běhu shora ohraničena polynomem ve vstupní velikosti algoritmu, tedy pro nějakou konstantu [1] [9] . Problémy , pro které existují deterministické polynomiální algoritmy, představují třídu složitosti P , která je ústředním bodem teorie výpočetní složitosti . Cobhamova teze uvádí, že polynomiální čas je synonymem pro „snadno zpracovatelný“, „schůdný“, „efektivní“ nebo „rychlý“ [10] . $T(n)=O(n^{k})$ $k$

Některé příklady polynomiálních algoritmů:

Algoritmus rychlého třídění celého čísla provádí maximální operace pro nějakou konstantu . Takže to funguje pro a je to polynomiální algoritmus. $n$ $An^{2}$ $A$ $O(n^{2})$
Všechny základní aritmetické operace (sčítání, odčítání, násobení, dělení a porovnávání) lze provádět v polynomiálním čase.
Maximální shodu v grafech lze nalézt v polynomiálním čase.

Striktně a slabě polynomiální čas

V některých kontextech, zvláště v optimalizaci , se rozlišuje mezi algoritmy striktního polynomiálního času a slabě polynomiálního času . Tyto dva koncepty platí pouze pro vstupy sestávající z celých čísel.

V aritmetickém modelu výpočtu je definován striktně polynomiální čas. V tomto modelu jsou základní aritmetické operace (sčítání, odčítání, násobení, dělení a porovnávání) brány jako jednotky provedení bez ohledu na délku operandů. Algoritmus pracuje v přísně polynomiálním čase, pokud [11]

počet operací v modelu aritmetického výpočtu je omezen na polynom v počtu celých čísel ve vstupním toku a
paměť používaná algoritmem je omezena polynomem ve velikostech vstupu.

Jakýkoli algoritmus s těmito dvěma vlastnostmi může být redukován na polynomiální časový algoritmus nahrazením aritmetických operací odpovídajícími algoritmy pro provádění aritmetických operací na Turingově stroji . Pokud nebude splněn druhý z výše uvedených požadavků, nebude to již pravda. Dané celé číslo (které zabírá paměť úměrnou n v Turingově stroji), to může být počítáno v n operacích používat opakované umocňování . Paměť použitá k reprezentaci je však úměrná a závisí spíše exponenciálně než polynomiálně na paměti použité pro vstup. Tudíž - je nemožné provádět tyto výpočty v polynomiálním čase na Turingově stroji, ale lze je provést v polynomiálním počtu aritmetických operací. $2^{n}$ $2^{{2^{n}}}$ $2^{{2^{n}}}$ $2^{n}$

Naopak existují algoritmy, které pracují v počtu kroků Turingova stroje, omezeného polynomickou délkou binárně zakódovaného vstupu, ale nepracují v počtu aritmetických operací, omezeném polynomem v počtu čísel v vstup. Jedním z příkladů je Euklidův algoritmus pro výpočet největšího společného dělitele dvou celých čísel. Pro dvě celá čísla je doba běhu algoritmu omezena kroky Turingova stroje. Toto číslo je polynom ve velikosti binární reprezentace čísel a , který může být zhruba reprezentován jako . Počet aritmetických operací přitom nelze omezit počtem celých čísel na vstupu (což je v tomto případě konstanta – na vstupu jsou pouze dvě čísla). S ohledem na tuto poznámku, algoritmus nefunguje v přísně polynomiálním čase. Skutečná doba běhu algoritmu závisí na hodnotách a , nejen na počtu celých čísel na vstupu. $A$ $b$ $O((\log \ a+\log \ b)^{2})$ $A$ $b$ $\log \a+\log\b$ $A$ $b$

Jestliže algoritmus běží v polynomiálním čase, ale ne striktně v polynomiálním čase, říká se, že běží ve slabě polynomiálním čase [12] . Známým příkladem problému, pro který je znám slabě polynomiální algoritmus, ale není znám žádný striktně polynomiální algoritmus, je lineární programování . Slabě polynomiální čas by neměl být zaměňován s pseudopolynomiálním časem .

Třídy obtížnosti

Pojem polynomiálního času vede k několika třídám složitosti v teorii výpočetní složitosti. Některé důležité třídy definované pomocí polynomiálního času jsou uvedeny níže.

P : Třída složitosti problémů řešitelnosti , které lze vyřešit v deterministickém Turingově stroji v polynomiálním čase.
NP : Třída složitosti problémů řešitelnosti, které lze vyřešit v nedeterministickém Turingově stroji v polynomiálním čase.
ZPP : Třída složitosti úloh řešitelnosti, které lze vyřešit s nulovou chybou v pravděpodobnostním Turingově stroji v polynomiálním čase.
RP : Třída složitosti problémů řešitelnosti, které lze vyřešit jednostrannými chybami v pravděpodobnostním Turingově stroji v polynomiálním čase.
BPP : Třída složitosti problémů řešitelnosti, které lze vyřešit s oboustrannými chybami v pravděpodobnostním Turingově stroji v polynomiálním čase.
BQP : Třída složitosti problémů řešitelnosti, které lze vyřešit s oboustrannými chybami v kvantovém Turingově stroji v polynomiálním čase.

P je nejmenší třída časové složitosti na deterministickém stroji, která je stabilní hlediska změny modelu stroje. (Například přechod z jednopáskového Turingova stroje na vícepáskový Turingův stroj může vést ke kvadratickému zrychlení, ale jakýkoli algoritmus, který běží v polynomiálním čase na jednom modelu, bude běžet v polynomiálním čase na jiném.)

Superpolynomiální čas

Říká se, že algoritmus běží v superpolynomiálním čase , pokud T ( n ) není shora ohraničeno polynomem. Tento čas je ω( n c ) pro všechny konstanty c , kde n je vstupní argument, obvykle počet vstupních bitů.

Například algoritmus, který má 2n kroků, vyžaduje superpolynomiální čas (konkrétněji exponenciální čas) pro vstup o velikosti n .

Je jasné, že algoritmus využívající exponenciální zdroje je superpolynomiální, ale některé algoritmy jsou velmi slabě superpolynomiální. Například Adleman-Pomerance-Rumeliho test primality běží v čase n O(log log n ) na n - bitovém vstupu. Toto roste rychleji než jakýkoli polynom pro dostatečně velké n , ale velikost vstupu se musí stát velmi velkou, aby v něm nedominoval polynom malého stupně.

Algoritmus vyžadující superpolynomiální čas leží mimo třídu složitosti P . Cobhamova teze uvádí, že tyto algoritmy jsou nepraktické a v mnoha případech jsou. Protože problém rovnosti tříd P a NP nebyl vyřešen, nejsou v současné době známy žádné algoritmy pro řešení NP-úplných problémů v polynomiálním čase.

Kvazipolynomiální čas

Algoritmy kvazipolynomiálního času jsou algoritmy , které běží pomaleji než polynomiální čas, ale ne tak pomalé jako algoritmy exponenciálního času. Nejhorší případ běhu pro kvazi-polynomiální algoritmus je stejný pro nějaké pevné c . Známý klasický algoritmus pro faktorizaci celého čísla, metoda obecného čísla pole sieve , která běží přibližně v čase , není kvazi-polynomiální, protože dobu běhu nelze reprezentovat jako pro nějaké pevné c . Pokud je konstanta "c" v definici kvazi-polynomiálního časového algoritmu 1, dostaneme polynomiální časový algoritmus, a pokud je menší než 1, dostaneme sublineární časový algoritmus. ${\displaystyle 2^{O((\log n)^{c)))))$ ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O((\log n)^{c)))))$

Algoritmy kvazi-polynomiálního času obvykle vznikají, když redukujeme NP-těžký problém na jiný problém. Můžete například vzít NP-těžký problém, řekněme 3SAT , a zredukovat ho na jiný problém B, ale velikost problému bude . V tomto případě redukce nedokazuje, že problém B je NP-těžký, taková redukce pouze ukazuje, že neexistuje žádný polynomiální algoritmus pro B, pokud neexistuje kvazi-polynomiální algoritmus pro 3SAT (a pak pro všechny NP -problémy) . Podobně existují některé problémy, pro které známe algoritmy s kvazi-polynomiálním časem, ale pro které neznáme algoritmy s polynomiálním časem. Takové problémy se objevují v aproximačních algoritmech. Slavným příkladem je orientovaný Steinerův problém , pro který existuje přibližný kvazi-polynomiální algoritmus s aproximačním koeficientem (kde n je počet vrcholů), ale existence polynomiálního algoritmu je otevřený problém. ${\displaystyle 2^{O((\log n)^{c)))))$ $O(\log ^{3}n)$

Třída složitosti QP se skládá ze všech problémů, které mají kvazi-polynomiální časové algoritmy. Může být definován z hlediska DTIME takto [13] :

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

Vztah k NP-úplným problémům

V teorii složitosti se nevyřešený problém rovnosti tříd P a NP ptá, zda všechny problémy z třídy NP mají polynomiální časové algoritmy řešení. Všechny dobře známé algoritmy pro NP-úplné problémy, jako je 3SAT, mají exponenciální čas. Navíc existuje domněnka, že pro mnoho přirozených NP-úplných problémů neexistují žádné algoritmy se subexponenciální dobou provádění. Zde je „subexponenciální čas“ brán ve smyslu druhé definice uvedené níže. (Na druhou stranu, mnoho problémů teorie grafů přirozeně reprezentovaných maticemi sousednosti je řešitelných v subexponenciálním čase jednoduše proto, že velikost vstupu je druhou mocninou počtu vrcholů.) Tato domněnka (pro problém k-SAT) je známá jako exponenciální časová domněnka [14] . Protože předpokládá, že NP-úplné problémy nemají kvazi-polynomiální časové algoritmy, některé výsledky neaproximovatelnosti v oblasti aproximačních algoritmů předpokládají, že NP-úplné problémy nemají kvazi-polynomiální časové algoritmy. Podívejte se například na známé výsledky týkající se nepřiblížení problému zakrytí sady .

Subexponenciální čas

Termín subexponenciální čas se používá k vyjádření toho, že doba provádění nějakého algoritmu může růst rychleji než jakýkoli polynom, ale zůstává podstatně kratší než exponenciální. V tomto smyslu jsou problémy se subexponenciálními časovými algoritmy poddajnější než algoritmy s pouze exponenciálním časem. Přesná definice „subexponenciály“ ještě není obecně přijímána [15] a níže uvádíme dvě nejběžnější definice.

První definice

Říká se, že problém je vyřešen v subexponenciálním čase, pokud je vyřešen algoritmem, jehož logaritmus doby běhu roste méně než jakýkoli daný polynom. Přesněji řečeno, problém má subexponenciální čas, pokud pro libovolné ε > 0 existuje algoritmus, který problém řeší v čase O(2 n ε ). Množinu všech takových problémů tvoří třída složitosti SUBEXP , kterou lze vyjádřit pomocí DTIME jako [3] [16] [17] [18] .

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

Všimněte si, že zde ε není součástí vstupních dat a každé ε může mít svůj vlastní algoritmus pro řešení problému.

Druhá definice

Někteří autoři definují subexponenciální čas jako průběžný čas 2 o( n ) [14] [19] [20] . Tato definice umožňuje delší dobu běhu než první definice. Příkladem takového sub-exponenciálního časového algoritmu je dobře známý klasický algoritmus pro faktorizaci celých čísel, metoda obecného čísla pole síta , která běží přibližně v čase , kde vstupní délka je n . Dalším příkladem je známý algoritmus pro problém isomorfismu grafu , jehož doba běhu je . ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O({\sqrt {n\log n))))$

Všimněte si, že je rozdíl, zda je algoritmus subexponenciální v počtu vrcholů nebo v počtu hran. V parametrizované složitosti je tento rozdíl explicitně přítomen zadáním páru , problému řešitelnosti a parametru k . SUBEPT je třída všech parametrizovaných problémů, které běží v subexponenciálním čase v k a v polynomiálním čase v n [21] : $(L,k)$

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

Přesněji řečeno, SUBEPT je třída všech parametrizovaných problémů , pro které existuje vyčíslitelná funkce c a algoritmus, který řeší L v čase . $(L,k)$ $f:\mathbb {N} \to \mathbb {N}$ $f\in o(k)$ $2^{f(k)}\cdot {\text{poly}}(n)$

Exponenciální časová domněnka

Exponenciální časový odhad (' ETH ) uvádí, že 3SAT , problém splnitelnosti pro booleovské formule v konjunktivní normální formě s maximálně třemi literály na větu a n proměnnými, nelze vyřešit v čase 2o ( n ) . Přesněji řečeno, domněnka říká, že existuje nějaká konstanta c >0 taková, že 3SAT nelze vyřešit v 2 cn na žádném deterministickém Turingově stroji. Jestliže m označuje počet vět, ETH je ekvivalentní hypotéze, že k -SAT nelze vyřešit v čase 2 o ( m ) pro žádné celé číslo k ≥ 3 [22] . Z exponenciální časové hypotézy vyplývá, že P ≠ NP .

Exponenciální čas

Říká se, že algoritmus běží v exponenciálním čase , pokud je T ( n ) nahoře ohraničeno 2 poly( n ) , kde poly( n ) je nějaký polynom v n . Více formálně, algoritmus běží v exponenciálním čase jestliže T ( n ) je ohraničený O(2 n k ) s nějakou konstantou k . Úlohy, které běží v exponenciálním čase na deterministických Turingových strojích, tvoří třídu složitosti EXP .

{\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)

Někdy se termín exponenciální čas používá pro algoritmy, pro které T ( n ) = 2 O( n ) , kde exponent je nanejvýš lineární funkcí n . Výsledkem je třída složitosti E .

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

Dvojitý exponenciální čas

Říká se, že algoritmus běží ve dvojnásobně exponenciálním čase, pokud je T ( n ) nahoře ohraničeno 2 2 poly( n ) , kde poly ( n ) je nějaký polynom v n . Takové algoritmy patří do třídy složitosti 2-EXPTIME .

{\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{2^{n^{c}}}})

Mezi známé dvojitě exponenciální algoritmy patří:

Postup výpočtu pro Presburgerovu aritmetiku
Výpočet Gröbnerovy báze (nejhorší případ [23] )
Eliminace kvantifikátorů v reálně uzavřených polích vyžaduje minimálně dvojnásobek exponenciální doby běhu [24] a lze ji provést za tuto dobu [25] .

Viz také

L zápis
Potíže s pamětí

Poznámky

↑ 12 Michael Sipser . Úvod do teorie počítání. - Course Technology Inc, 2006. - ISBN 0-619-21764-2 .
↑ Kurt Mehlhorn, Stefan Naher. Ohraničené uspořádané slovníky v O(log log N) čase a O(n) prostoru // Information Processing Letters. - 1990. - T. 35 , no. 4 . - S. 183 . - doi : 10.1016/0020-0190(90)90022-P .
↑ 1 2 László Babai, Lance Fortnow, N. Nisan, Avi Wigderson. BPP má subexponenciální časové simulace, pokud EXPTIME nemá publikovatelné důkazy // Computational Complexity. - Berlín, New York: Springer-Verlag , 1993. - Vol. 3 , č. 4 . - S. 307-318 . - doi : 10.1007/BF01275486 .
↑ JE Rawlins, Gregory E. Shannon. Efektivní řazení maticového řetězce v Polylog Time // SIAM Journal on Computing. - Philadelphia: Společnost pro průmyslovou a aplikovanou matematiku , 1998. - V. 27 , no. 2 . - S. 466-490 . — ISSN 1095-7111 . - doi : 10.1137/S0097539794270698 .
↑ Ravi Kumar, Ronitt Rubinfeld. Algoritmy sublineárního času // Zprávy SIGACT. - 2003. - T. 34 , no. 4 . - S. 57-67 . - doi : 10.1145/954092.954103 .
↑ DR KN PRASANNA KUMAR, PROF BS KIRANAGI A PROF CS BAGEWADI. OBECNÁ TEORIE SYSTÉMU „KVANTOVÉ INFORMACE – KVANTOVÉ PROPOJENÍ, ROZPAD SUBATOMICKÝCH ČÁSTIC – STAVY ASYMETRICKÉHO SPINU, LOKÁLNĚ SKRYTÉ PROMĚNNÉ – ZŘETĚZITÝ MODEL // International Journal of Scientific and Research Publications. - červenec 2012. - svazek 2 , č. 7 . — ISSN 22503153 .
↑ Ashish V. Naik, Kenneth W. Regan, D. Sivakumar. O kvazilineární teorii časové složitosti // Teoretická informatika. — Sv. 148 . - str. 325-349 .
↑ Sedgewick, R. a Wayne K (2011). Algorithms, 4th Ed Archived 15 July 2014 at Wayback Machine . p. 186. Pearson Education, Inc.
↑ Christos H. Papadimitriou. Výpočetní složitost. - Reading, Mass.: Addison-Wesley, 1994. - ISBN 0-201-53082-1 .
↑ Alan Cobham. Proč. Logika, metodologie a filozofie vědy II. - Severní Holandsko, 1965. - C. Vnitřní výpočetní obtížnost funkcí.
↑ Martin Grötschel, László Lovász , Alexander Schrijver . Geometrické algoritmy a kombinatorická optimalizace. - Springer, 1988. - C. Složitost, věštci a numerické výpočty. — ISBN 0-387-13624-X .
↑ Alexander Schrijver. Kombinatorická optimalizace: Mnohostěn a účinnost. - Springer, 2003. - V. 1. - C. Úvod k algoritmům a složitosti. — ISBN 3-540-44389-4 .
↑ Complexity Zoo Archived 26. července 2010 na Wayback Machine Class QP: Quasipolynomial-Time Archived 22. prosince 2015 na Wayback Machine
↑ 1 2 R. Impagliazzo, R. Paturi. O složitosti k-SAT // Journal of Computer and System Sciences. - Elsevier , 2001. - T. 62 , no. 2 . - S. 367-375 . — ISSN 1090-2724 . doi : 10.1006 / jcss.2000.1727 .
↑ Aaronson, Scott. Ne úplně exponenciální dilema. — 5. dubna 2009.
↑ Complexity Zoo Archived 26. července 2010 na Wayback Machine Class SUBEXP: Deterministic Subexponencial-Time Archived 27. srpna 2016 na Wayback Machine
↑ P. Moser. Bare's Categories on Small Complexity Classes // Lecture Notes in Computer Science . - Berlín, New York: Springer-Verlag, 2003. - S. 333-342 . — ISSN 0302-9743 .
↑ PB Miltersen. DERANDOMIZACE SLOŽITÝCH TŘÍD // Handbook of Randomized Computing. - Kluwer Academic Pub, 2001. - S. 843 .
↑ Greg Kuperberg. Kvantový algoritmus s exponenciálním časem pro problém dihedrální skryté podskupiny // SIAM Journal on Computing. - Philadelphia: Společnost pro průmyslovou a aplikovanou matematiku , 2005. - V. 35 , no. 1 . - S. 188 . — ISSN 1095-7111 . - doi : 10.1137/s0097539703436345 .
↑ Oded Regev. Subexponenciální časový algoritmus pro problém dihedrální skryté podskupiny s polynomiálním prostorem . — 2004.
↑ Jörg Flum, Martin Grohe. Teorie parametrizované složitosti. - Springer, 2006. - S. 417. - ISBN 978-3-540-29952-3 .
↑ R. Impagliazzo, R. Paturi, F. Zane. Které problémy mají silně exponenciální složitost? // Journal of Computer and System Sciences . - 2001. - T. 63 , no. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
↑ Mayr, E. & Mayer, A. Složitost slovní úlohy pro komutativní pologrupy a polynomiální ideály // Adv. v matematice.. - 1982. - Vydání. 46 . - S. 305-329 .
↑ JH Davenport, J. Heintz. Eliminace reálného kvantifikátoru je dvojnásobně exponenciální // J. Symbolic Comp.. - 1988. - Vol. 5 . - S. 29-35 . .
↑ G.E. Collins. Proč. 2. Teorie automatů konference GI a formální jazyky. — Springer. - T. 33. - S. 134-183. — (Poznámky z informatiky).