Algoritmens tidskomplexitet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 juni 2022; kontroller kräver 3 redigeringar .

Inom datavetenskap definieras tidskomplexiteten för en algoritm som en funktion av längden på strängen som representerar ingången, lika med algoritmens gångtid på den givna ingången [1] . Tidskomplexiteten för en algoritm uttrycks vanligtvis med den stora "O" -notationen , som endast tar hänsyn till termen av högsta ordningen och inte heller tar hänsyn till konstanta faktorer, dvs koefficienter. Om komplexiteten uttrycks på detta sätt talar man om en asymptotisk beskrivning av tidskomplexiteten, det vill säga eftersom storleken på ingången tenderar till oändligheten. Till exempel, om det finns ett antal så att körtiden för algoritmen för alla inmatningar av längd inte överstiger $n_{0}$ $n>n_{0}$ $5n^{3}+3n$ , då kan tidskomplexiteten för denna algoritm asymptotiskt uppskattas till . $O(n^{3})$

Tidskomplexitet uppskattas vanligtvis genom att räkna antalet elementära operationer som utförs av algoritmen. Utförandetiden för en sådan operation tas som en konstant, det vill säga den uppskattas asymptotiskt som . I sådan notation skiljer sig den totala exekveringstiden och antalet elementära operationer som utförs av algoritmen med maximalt en konstant faktor, vilket inte tas med i beräkningen i O-notationen. Eftersom körtiden för algoritmen kan skilja sig åt på ingångar av samma storlek, används vanligtvis den värsta körtiden , som betecknas som och definieras som den längsta körtiden för algoritmen över alla ingångslängder . Mer sällan, och detta anges vanligtvis specifikt, beräknas den genomsnittliga komplexiteten , det vill säga den matematiska förväntan av körtiden för alla möjliga ingångar. Drifttiden för en algoritm kan klassificeras beroende på vilken funktion som är under O-notation. Till exempel kallas en algoritm med en algoritm med linjär körtid , och en algoritm med för vissa kallas polynom . $O(1)$ $T(n)$ $n$ $T(n)\in O(n)$ $T(n)\in O(n^{\alpha })$ $\alfa >1$

Tidtabell för svårigheter

Följande tabell sammanfattar de vanligaste komplexitetsklasserna . I tabellen , Betecknar ett godtyckligt polynom i , det vill säga . $poly(x)$ $x$ ${\displaystyle poly(x)=x^{O(1)))$

namn	Svårighetsklass	Arbetstimmar, $T(n)$	Arbetstidsexempel	Algoritmexempel
konstant tid		$O(1)$	$tio$	Bestämma pariteten för ett heltal (representerat i binärt)
omvänd Ackermann-funktion		$O(\alpha (n))$		Amorteringsanalys per operation med hjälp av osammanhängande uppsättningar
itererad logaritmisk tid		$O(\log ^{*}n)$		Distribuerade cykelfärger
dubbel logaritmisk		$O(\log \log n)$		Amorteringstid per operation vid användning av begränsad prioritetskö [2]
logaritmisk tid	DLOGTIME	$O(\log n)$	$\log n$ , $\log n^{2}$	Binär sökning
polylogaritmisk tid		$poly(\log n)$	${\displaystyle (\log n)^{2))$
sublinjär tid		$O(n^{c})$ på $0<c<1$	$n^{1/2}$ , $n^{2/3}$	Sök i ett k-dimensionellt träd
linjär tid		$På)$	$n$	Hitta det minsta eller största elementet i en osorterad array
"n log-asterisk n"		$O(n\log ^{*}n)$		Seidel polygon trianguleringsalgoritm [ .
linjär-logaritmisk tid		$O(n\log n)$	$n\log n$ , $\log n!$	Snabbaste jämförelsesorteringen
kvadratisk tid		$O(n^{2})$	$n^{2}$	Bubbelsortering , insättningssortering , rak vikning
kubiktid		$O(n^{3})$	$n^3$	Den vanliga multiplikationen av två matriser. Beräkning av partiell korrelation . $n\ gånger n$
polynomtid	P	$2^{O(\log n)}=poly(n)$	$n$ ... _ $n\log n$ ${\displaystyle n^{10))$	Karmarkars algoritm för linjär programmering , AKS-enkelhetstest
kvasi-polynomisk tid	QP	${\displaystyle 2^{poly(\log n)))$	${\displaystyle n^{\log \log n))$ , ${\displaystyle n^{\log n))$	Den snabbaste kända är approximationsalgoritmen för det orienterade Steinerproblemet . $O(\log ^{2}n)$
subexponentiell tid (första definition)	SUBEXP	$O(2^{n^{\varepsilon )))$ för alla $\varepsilon >0$	$2^{\log n^{\log \log n))$	Om man antar teoretiska hypoteser, finns BPP i SUBEXP. [3]
subexponentiell tid (andra definition)		$2^{o(n)}$	$2^{n^{1/3}}$	Snabbaste kända algoritmer för att faktorisera heltal och kontrollera grafisomorfism
exponentiell tid (med linjär exponent)	E	$2^{O(n)}$	$1.1^{n}$ , $10^{n}$	Lösning av resande säljarproblem med dynamisk programmering
exponentiell tid	EXPTIME	${\displaystyle 2^{poly(n)))$	$2^{{n}}$ , $2^{n^{2))$	Lösa problemet med matrismultiplikationsordningen med hjälp av uttömmande uppräkning
faktoriell tid		$O(n!)$	$n!$	Löser problemet med resande säljare genom uttömmande sökning
dubbel exponentiell tid	2-EXPTIME	$2^{2^{poly(n)))$	$2^{{2^{n}}}$	Kontrollera riktigheten av ett givet påstående i Presburger aritmetik
		${\sqrt[{n}]{\log _{n}(n)))$	1 för n >= 1

Konstant tid

En algoritm sägs vara en konstanttidsalgoritm (skriven som tid ) om värdet är begränsat till ett värde oberoende av storleken på ingången. Till exempel, att få ett enskilt element i en array tar konstant tid eftersom ett enda kommando exekveras för att hitta det. Att hitta minimivärdet i en osorterad array är dock inte en konstanttidsoperation eftersom vi måste titta på varje element i arrayen. Således tar denna operation linjär tid, . Om antalet element är känt i förväg och inte ändras, kan en sådan algoritm hänvisas till som en konstanttidsalgoritm. $O(1)$ $T(n)$ $På)$

Trots namnet "konstant tid" behöver inte löptiden vara oberoende av uppgiftens storlek, utan en övre gräns för löptiden borde. Till exempel, problemet med att "byta ut värdena på och , om nödvändigt, för att få resultatet " anses vara ett konstanttidsproblem, även om algoritmens körtid kan bero på om ojämlikheten redan håller eller inte. Det finns dock en konstant för vilken exekveringstiden för uppgiften aldrig överstiger . $a$ $b$ $a\leq b$ $a\leq b$ $t$ $t$

Nedan är ett exempel på kod som körs i konstant tid:

int index = 5; int item = lista[index]; om (villkoret är sant) då utföra vissa operationer med konstant gångtid annan utföra vissa operationer med konstant gångtid för i = 1 till 100 för j = 1 till 200 utföra vissa operationer med konstant gångtid

Om lika med , där är en konstant, är detta lika med lika med . $T(n)$ $O(\alpha )$ $\alfa$ $T(n)$ $O(1)$

Logaritmisk tid

En algoritm sägs köras i logaritmisk tid om . Eftersom datorer använder det binära talsystemet är basen för logaritmen (det vill säga ). Men när du ändrar basen för logaritmen och skiljer sig endast med en konstant faktor , som förkastas i O-big notation. Sålunda är standardnotationen för logaritmiska tidsalgoritmer oavsett basen för logaritmen. $T(n)=O(\log n)$ $2$ $\log _{2}n$ $\log _{a}n$ $\log _{b}n$ $\log_b a$ $O(\log n)$

Algoritmer som körs i logaritmisk tid finns vanligtvis i operationer på binära träd eller när du använder binär sökning .

$O(\log n)$ Algoritmer för att arbeta med arrayer av storleksdata anses vara mycket effektiva, eftersom förhållandet mellan exekveringstiden för en operation och storleken på arrayen minskar när denna storlek ökar. $n$

Ett mycket enkelt exempel på en sådan algoritm är att slå upp ord i en ordbok. Överväg en ordbok som innehåller ord sorterade i alfabetisk ordning. Samtidigt antar vi att alla ord har längd och att vi kan komma åt vilket element som helst i ordboken efter index i konstant tid. Låt vara det -: e elementet i ordboken, då kan du kontrollera om ordet finns i ordboken bortom . För att göra detta, överväga ordbokselementet , där anger avrundning nedåt numret . Om , då ska vi gå till höger halva av arrayen, annars - till vänster. I slutet får vi indexet för det första ordet, som är lika med eller lexikografiskt större än . $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 ( vektor < sträng > & D , sträng w ) { int n = D . storlek (); int l = -1 , r = n ; while ( r - l > 1 ) { int m = ( l + r ) / 2 ; if ( D [ m ] < w ) { l = m ; } annat { r = m ; } } returnera r ; }

Polylogaritmisk tid

En algoritm sägs köra i polylogaritmisk tid om för vissa . Till exempel kan problemet med matrismultiplikationsordningen lösas i en sådan tid på en parallell RAM-maskin [4] . $T(n)=O(\log ^{k}n)$ $k$

Sublinjär tid

En algoritm sägs köras i sublinjär tid om . I synnerhet inkluderar detta algoritmer vars tidskomplexitet är som ovan, samt till exempel Grovers sökning med komplexitet . $T(n)=o(n)$ $O(n^{{1/2}})$

Vanligtvis använder algoritmer som, även om de är exakta, fortfarande körs i sublinjär tid, processparallellism (liksom NC 1 - matrisdeterminantberäkningsalgoritmen), icke-klassiska beräkningar (som i Grovers sökning) eller har en garanterad gissning om indatastrukturen (som binära sökalgoritmer och många trädbearbetningsalgoritmer). Men formella språk som språket för ord som har en 1 bit i den position som bestäms av de första bitarna av ordet kan vara avgörbara i sublinjär tid även om vilken bit som helst kan vara viktig för att avgöra om ett ord tillhör ett språk . $\log n$

Termen sublinjär körtidsalgoritm används vanligtvis för algoritmer som, till skillnad från exemplen ovan, körs på konventionella sekventiella maskinmodeller och inte kräver a priori kunskap om ingångsstrukturen [5] . De får dock använda probabilistiska metoder , och ännu mer måste de ofta randomiseras för alla icke-triviella uppgifter.

Eftersom en sådan algoritm måste ge ett svar utan att helt läsa indata, är den mycket beroende av de åtkomstmetoder som tillåts i ingångsströmmen. Vanligtvis, för en ström som är en bitsträng , antas det att algoritmen kan begära ett värde för vilken som helst . ${\displaystyle b_{1},\dots ,b_{k))$ $O(1)$ $bi}$ $i$

Sublinjära tidsalgoritmer är vanligtvis probabilistiska och ger endast en ungefärlig lösning. Sublinjära körtidsalgoritmer uppstår naturligt när man utforskar egenskapskontroll .

Linjär tid

En algoritm sägs köras i linjär tid eller i tid om dess komplexitet är . Informellt innebär detta att för en tillräckligt stor ingångsstorlek ökar körtiden linjärt med storleken på ingången. Till exempel tar en procedur som summerar alla element i en lista tid proportionell mot listans längd. Denna beskrivning är inte helt korrekt, eftersom körtiden kan skilja sig betydligt från den exakta proportionaliteten, särskilt för små värden på . $På)$ $På)$ $n$

Linjär tid ses ofta som ett önskvärt attribut för en algoritm [6] . Mycket forskning har gjorts för att skapa algoritmer med (nästan) linjära eller bättre körtider. Dessa studier inkluderade både mjukvara och hårdvara. När det gäller hårdvaruexekvering kan vissa algoritmer som, ur en matematisk synvinkel, aldrig kan uppnå linjär exekveringstid i standardberäkningsmodeller , köras i linjär tid. Det finns vissa hårdvarutekniker som använder parallellitet för att uppnå detta mål. Ett exempel är associativt minne . Detta koncept med linjär tid används i mönstermatchningsproblem som Boyer–Moore- algoritmen och Ukkonens algoritm .

Kvasilinjär tid

En algoritm sägs köras i kvasilinjär tid om det är för någon konstant . När man talar om linjär-logaritmisk tid [7] . När det gäller soft-O skrivs sådan körtid som . För algoritmer med kvasi-linjär körtid är uppskattningen för någon också sann . Således är dessa algoritmer snabbare än något polynom i , vars grad är större än . $T(n)=O(n\log ^{k}n)$ $k$ $k=1$ ${\tilde {O}}(n)$ $T(n)\in o(n^{1+\varepsilon })$ $\varepsilon >0$ $n$ $ett$

Algoritmer som körs i kvasi-linjär tid, förutom de linjär-logaritmiska algoritmerna som nämns ovan, inkluderar:

In-place merge sort : ; $O(n\log ^{2}n)$
Snabbsortering : den matematiska förväntningen på körtiden för den probabilistiska versionen av algoritmen ligger i vilken ingång som helst, för den deterministiska versionen är denna uppskattning endast korrekt i genomsnitt över alla indata; $O(n\log n)$
Heap sort , merge sort , introsort , binary tree sort , fluent sort , solitaire sort och andra: värsta fall; $O(n\log n)$
Snabb Fourier Transform : ; $O(n\log n)$
Algoritmer på Monge-matriser : . $O(n\log n)$

Linjär-logaritmisk tid

Linjär-logaritmisk är ett specialfall av kvasi-linjär tid med en exponent på en logaritmisk faktor. $k=1$

En linjär-logaritmisk funktion är en funktion av formen (det vill säga produkten av en linjär och en logaritmisk term). Algoritmen sägs köras i linjär-logaritmisk tid om [8] . Således växer en linjär-logaritmisk funktion snabbare än en linjär, men långsammare än något polynom av grad större än . $n\log n$ $T(n)=O(n\log n)$ $n$ $ett$

I många fall är körtiden helt enkelt resultatet av att utföra en tidsoperation på gångtiden . Till exempel, sortering med ett binärt träd skapar ett binärt träd genom att infoga varje element i en matris av storlek i det en efter en. Eftersom infogningsoperationen i ett balanserat binärt sökträd tar tid kommer den totala exekveringstiden för algoritmen att vara linjär-logaritmisk. $n\log n$ $n$ $O(\log n)$ $n$ $O(\log n)$

Varje jämförelsebaserad sortering kräver åtminstone ett linjärt-logaritmiskt antal jämförelser i värsta fall. En av de enkla motiveringarna för detta faktum ur informationsteoretisk synvinkel ser ut så här: som ett resultat av sortering får vi en permutation av längd , som unikt bestämmer ordningen på elementen. Det finns olika sorteringar totalt, om vi entydigt vill koda var och en av dem med någon sekvens av bitar behöver vi i genomsnitt inte mindre än bitar av information per permutation. I det här fallet är resultatet av en parvis jämförelse av två matriselement exakt en informationsbit - antingen är det första elementet mindre än det andra eller inte. Således, om vi endast använder parvisa jämförelser för sortering, är det inte möjligt att sortera en array i bättre än värsta fall. Samtidigt uppstår en sådan uppskattning för många rekursiva sorteringar, såsom merge sort , ofta från en rekursiv ekvation . $n$ $n!$ $\log n!\sim n\log n$ $O(n\log n)$ $T(n)=T(n/2)+O(n)$

Delkvadrat tid

En algoritm sägs köras i subkvadratisk tid om . $T(n)=o(n^{2})$

Till exempel är enkla sorteringsalgoritmer baserade på jämförelser (som insättningssortering ) kvadratiska. Samtidigt kan mer avancerade algoritmer hittas som har subquadratisk körtid (t.ex. Shell sort ). Inga generella sorteringar fungerar i linjär tid, men övergången från kvadratisk till subkvadratisk tid är av stor praktisk betydelse.

Polynomtid

En algoritm sägs gå i polynomtid om körtiden är avgränsad ovanifrån av ett polynom i algoritmens indatastorlek, det vill säga för någon konstant [1] [9] . De problem för vilka deterministiska polynom-tidsalgoritmer existerar utgör komplexitetsklassen P , som är central för beräkningskomplexitetsteorin . Cobhams avhandling säger att polynomtid är synonymt med "lätt att bearbeta", "möjlig", "effektiv" eller "snabb" [10] . $T(n)=O(n^{k})$ $k$

Några exempel på polynomalgoritmer:

Heltalsquicksort- algoritmen gör maximala operationer för en konstant . Så det fungerar för och är en polynomalgoritm. $n$ $An^{2}$ $A$ $O(n^{2})$
Alla grundläggande aritmetiska operationer (addition, subtraktion, multiplikation, division och jämförelse) kan utföras i polynomtid.
Den maximala matchningen i grafer kan hittas i polynomtid.

Strikt och svagt polynomisk tid

I vissa sammanhang, särskilt inom optimering , skiljer man mellan strikt polynomtid och svagt polynomtidsalgoritmer . Dessa två begrepp gäller endast indata som består av heltal.

Strikt polynomtid definieras i den aritmetiska beräkningsmodellen. I denna modell tas de grundläggande aritmetiska operationerna (addition, subtraktion, multiplikation, division och jämförelse) som exekveringsenheter, oavsett längden på operanderna. Algoritmen fungerar i strikt polynomisk tid om [11]

antalet operationer i den aritmetiska beräkningsmodellen är begränsat till ett polynom i antalet heltal i ingångsströmmen, och
minnet som används av algoritmen begränsas av ett polynom i storleken på ingången.

Alla algoritmer med dessa två egenskaper kan reduceras till en polynomisk tidsalgoritm genom att ersätta aritmetiska operationer med motsvarande algoritmer för att utföra aritmetiska operationer på en Turing-maskin . Om det andra av ovanstående krav inte uppfylls kommer detta inte längre att vara sant. Givet ett heltal (som upptar ett minne som är proportionellt mot n i en Turing-maskin), kan det beräknas i n operationer med upprepad exponentiering . Minnet som används för att representera är dock proportionellt mot , och det beror exponentiellt snarare än polynomiskt på minnet som används för inmatning. Därför - det är omöjligt att utföra dessa beräkningar i polynomtid på en Turing-maskin, men det kan utföras i ett polynomantal av aritmetiska operationer. $2^{n}$ $2^{{2^{n}}}$ $2^{{2^{n}}}$ $2^{n}$

Omvänt finns det algoritmer som fungerar i antalet steg i Turing-maskinen, begränsat av polynomets längd på den binärkodade ingången, men som inte fungerar i antalet aritmetiska operationer, begränsat av polynomet i antalet tal i inmatning. Euklids algoritm för att beräkna den största gemensamma divisorn av två heltal är ett exempel. För två heltal och algoritmens gångtid begränsas av Turing-maskinens steg. Detta nummer är ett polynom i storleken på den binära representationen av tal och , som grovt kan representeras som . Samtidigt kan antalet aritmetiska operationer inte begränsas av antalet heltal i ingången (vilket i det här fallet är en konstant - det finns bara två tal i inmatningen). Med tanke på denna anmärkning fungerar inte algoritmen i strikt polynomisk tid. Algoritmens verkliga körtid beror på värdena och , och inte bara på antalet heltal i ingången. $a$ $b$ $O((\log \ a+\log \ b)^{2})$ $a$ $b$ $\log \a+\log\b$ $a$ $b$

Om en algoritm körs i polynomtid men inte strikt polynomtid, sägs den köras i svag polynomtid [12] . Ett välkänt exempel på ett problem för vilket en svag polynomalgoritm är känd men ingen strikt polynomalgoritm är känd är linjär programmering . Svag polynomtid ska inte förväxlas med pseudopolynomtid .

Svårighetsklasser

Begreppet polynomtid leder till flera komplexitetsklasser inom beräkningskomplexitetsteorin. Några viktiga klasser definierade med polynomtid listas nedan.

P : Komplexitetsklass för lösbarhetsproblem som kan lösas i en deterministisk Turingmaskin i polynomtid.
NP : Komplexitetsklass för lösbarhetsproblem som kan lösas i en icke-deterministisk Turingmaskin i polynomtid.
ZPP : Komplexitetsklass för lösbarhetsproblem som kan lösas med noll fel i en probabilistisk Turingmaskin i polynomtid.
RP : Komplexitetsklass av lösbarhetsproblem som kan lösas med ensidiga fel i en probabilistisk Turingmaskin i polynomtid.
BPP : Komplexitetsklass för lösbarhetsproblem som kan lösas med dubbelsidiga fel i en probabilistisk Turingmaskin i polynomtid.
BQP : Komplexitetsklass för lösbarhetsproblem som kan lösas med dubbelsidiga fel i en kvantturingmaskin i polynomtid.

P är den minsta tidskomplexitetsklassen på en deterministisk maskin som är stabil det gäller att ändra maskinmodellen. (Till exempel att gå från en Turing-maskin med ett band till en Turing-maskin med flera band kan resultera i en kvadratisk hastighet, men alla algoritmer som körs i polynomtid på en modell kommer att köras i polynomtid på en annan.)

Superpolynomisk tid

Algoritmen sägs köras i superpolynomisk tid , om T ( n ) inte begränsas ovanifrån av ett polynom. Denna tid är ω( n c ) för alla konstanter c , där n är ett inmatningsargument, vanligtvis antalet inmatade bitar.

Till exempel kräver en algoritm som tar 2n steg superpolynomisk tid (mer specifikt exponentiell tid) för en indata av storleken n .

Det är tydligt att en algoritm som använder exponentiella resurser är superpolynom, men vissa algoritmer är mycket svagt superpolynomiska. Till exempel körs Adleman-Pomerance-Rumeli-primalitetstestet på n O(log log n ) -tid på en n -bitars ingång. Detta växer snabbare än något polynom för tillräckligt stort n , men storleken på ingången måste bli mycket stor så att den inte domineras av ett polynom i liten grad.

En algoritm som kräver superpolynomisk tid ligger utanför komplexitetsklassen P . Cobhams avhandling säger att dessa algoritmer är opraktiska, och i många fall är de det. Eftersom problemet med jämlikhet mellan klasserna P och NP inte har lösts, är för närvarande inga algoritmer kända för att lösa NP-kompletta problem i polynomtid.

Kvasipolynomisk tid

Kvasipolynomiska tidsalgoritmer är algoritmer som går långsammare än polynomtiden, men inte lika långsamt som exponentiella tidsalgoritmer. Den värsta körtiden för en kvasipolynomalgoritm är lika för vissa fasta c . En välkänd klassisk algoritm för att faktorisera ett heltal, den allmänna talfältssiktmetoden , som körs i ungefär tiden , är inte kvasipolynom eftersom körtiden inte kan representeras som för vissa fasta c . Om konstanten "c" i definitionen av den kvasipolynomiska tidsalgoritmen är 1 får vi polynomtidsalgoritmen, och om den är mindre än 1 får vi den sublinjära tidsalgoritmen. ${\displaystyle 2^{O((\log n)^{c)))))$ ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O((\log n)^{c)))))$

Kvasi-polynom-tidsalgoritmer uppstår vanligtvis när man reducerar ett NP-hårt problem till ett annat problem. Till exempel kan du ta ett NP-hårt problem, säg 3SAT , och reducera det till ett annat problem B, men storleken på problemet blir . I det här fallet bevisar inte reduktionen att problem B är NP-hårt, en sådan reduktion visar bara att det inte finns någon polynomalgoritm för B, såvida det inte finns en kvasipolynomalgoritm för 3SAT (och då för alla NP -problem) . På liknande sätt finns det några problem för vilka vi känner till algoritmer med kvasipolynomtid, men för vilka algoritmer med polynomtid är okända. Sådana problem förekommer i approximationsalgoritmer. Ett känt exempel är det orienterade Steiner-problemet , för vilket det finns en ungefärlig kvasipolynomalgoritm med en approximationskoefficient (där n är antalet hörn), men förekomsten av en polynomtidsalgoritm är ett öppet problem. ${\displaystyle 2^{O((\log n)^{c)))))$ $O(\log ^{3}n)$

Komplexitetsklassen QP består av alla problem som har kvasipolynomiska tidsalgoritmer. Det kan definieras i termer av DTIME enligt följande [13] :

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

Relation till NP-kompletta problem

I komplexitetsteorin frågar det olösta problemet med likheten mellan klasserna P och NP om alla problem från klassen NP har polynomiska tidslösningsalgoritmer. Alla välkända algoritmer för NP-kompletta problem, som 3SAT, har exponentiell tid. Dessutom finns det en gissning att för många naturliga NP-kompletta problem finns det inga algoritmer med subexponentiell exekveringstid. Här tas "subexponentiell tid" i betydelsen av den andra definitionen som ges nedan. (Å andra sidan är många grafteoriproblem som naturligt representeras av närliggande matriser lösbara i subexponentiell tid helt enkelt för att storleken på ingången är kvadraten på antalet hörn.) Denna gissning (för k-SAT-problemet) är känd som den exponentiella tidsförmodan [14] . Eftersom det antas att NP-kompletta problem inte har kvasipolynomiska tidsalgoritmer, antar vissa icke-approximerbarhetsresultat inom området för approximationsalgoritmer att NP-kompletta problem inte har kvasipolynomiska tidsalgoritmer. Se till exempel välkända resultat om det icke-närbarhetsproblem som täcker uppsättningen .

Subexponentiell tid

Termen subexponentiell tid används för att uttrycka att exekveringstiden för en viss algoritm kan växa snabbare än något polynom, men förblir väsentligt mindre än exponentiellt. I denna mening är problem med subexponentiella tidsalgoritmer mer formbara än algoritmer med endast exponentiell tid. Den exakta definitionen av "subexponentiell" är ännu inte allmänt accepterad [15] , och vi ger nedan två av de vanligaste definitionerna.

Första definitionen

Ett problem sägs lösas i subexponentiell tid om det löses med en algoritm vars logaritm för löptiden växer mindre än ett givet polynom. Mer exakt, ett problem har subexponentiell tid om det för någon ε > 0 finns en algoritm som löser problemet i O(2 n ε ) tid. Uppsättningen av alla sådana problem utgör komplexitetsklassen SUBEXP , som kan uttryckas i termer av DTIME som [3] [16] [17] [18] .

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

Observera att här är ε inte en del av indata, och varje ε kan ha sin egen algoritm för att lösa problemet.

Andra definitionen

Vissa författare definierar subexponentiell tid som körtiden 2 o( n ) [14] [19] [20] . Denna definition tillåter en längre drifttid än den första definitionen. Ett exempel på en sådan sub-exponentiell tidsalgoritm är den välkända klassiska algoritmen för att faktorisera heltal, den allmänna talfältssiktmetoden , som körs i ungefär tiden , där ingångslängden är n . Ett annat exempel är den välkända algoritmen för grafisomorfismproblemet , vars körtid är . ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O({\sqrt {n\log n))))$

Observera att det finns en skillnad om algoritmen är subexponentiell i antalet hörn eller antalet kanter. I parameteriserad komplexitet är denna skillnad explicit närvarande genom att specificera paret , lösbarhetsproblemet och parametern k . SUBEPT är klassen för alla parametriserade problem som körs i subexponentiell tid i k och i polynomtid i n [21] : $(L,k)$

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

Mer exakt är SUBEPT klassen av alla parametriserade problem för vilka det finns en beräkningsbar funktion c och en algoritm som löser L i tid . $(L,k)$ $f:\mathbb {N} \to \mathbb {N}$ $f\in o(k)$ $2^{f(k)}\cdot {\text{poly}}(n)$

Den exponentiella tidsförmodan

Den exponentiella tidsförmodan (' ETH )' anger att 3SAT , tillfredsställbarhetsproblemet för booleska formler i konjunktiv normalform med maximalt tre bokstaver per mening och n variabler, inte kan lösas i tid 2o ( n ) . Mer exakt säger gissningarna att det finns någon konstant c >0 så att 3SAT inte kan lösas i 2 cn på någon deterministisk Turing-maskin. Om m anger antalet meningar är ETH ekvivalent med hypotesen att k -SAT inte kan lösas i tiden 2 o ( m ) för något heltal k ≥ 3 [22] . Av den exponentiella tidshypotesen följer att P ≠ NP .

Exponentiell tid

En algoritm sägs köras i exponentiell tid om T ( n ) ovanför begränsas av 2 poly( n ) , där poly( n ) är något polynom i n . Mer formellt körs algoritmen i exponentiell tid om T ( n ) är begränsad till O( 2nk ) med någon konstant k . Uppgifter som körs i exponentiell tid på deterministiska Turing-maskiner bildar EXP -komplexitetsklassen .

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

Ibland används termen exponentiell tid för algoritmer där T ( n ) = 2 O( n ) , där exponenten som mest är en linjär funktion av n . Detta resulterar i komplexitetsklassen E .

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

Dubbel exponentiell tid

En algoritm sägs köras i dubbel exponentiell -tid om T ( n ) ovanför avgränsas av 2 2 poly( n ) , där poly( n ) är något polynom i n . Sådana algoritmer tillhör komplexitetsklassen 2-EXPTIME .

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

Välkända dubbelexponentiella algoritmer inkluderar:

Beräkningsprocedur för Presburger aritmetik
Beräkna Gröbner-basen (värsta fall [23] )
Eliminering av kvantifierare i reellt slutna fält kräver minst två gånger den exponentiella körtiden [24] och kan göras under denna tid [25] .

Se även

L-notation
Minnessvårigheter

Anteckningar

↑ 12 Michael Sipser . Introduktion till teorin om beräkning. - Course Technology Inc, 2006. - ISBN 0-619-21764-2 .
↑ Kurt Mehlhorn, Stefan Naher. Begränsade ordnade ordböcker i O(log log N) tid och O(n) mellanrum // Information Processing Letters. - 1990. - T. 35 , nr. 4 . - S. 183 . - doi : 10.1016/0020-0190(90)90022-P .
↑ 1 2 László Babai, Lance Fortnow, N. Nisan, Avi Wigderson. BPP har subexponentiella tidssimuleringar om inte EXPTIME har publicerbara bevis // Computational Complexity. - Berlin, New York: Springer-Verlag , 1993. - Vol. 3 , nr. 4 . - S. 307-318 . - doi : 10.1007/BF01275486 .
↑ JE Rawlins, Gregory E. Shannon. Effektiv matriskedjeordning i Polylog Time // SIAM Journal on Computing. - Philadelphia: Society for Industrial and Applied Mathematics , 1998. - V. 27 , nr. 2 . - S. 466-490 . — ISSN 1095-7111 . - doi : 10.1137/S0097539794270698 .
↑ Ravi Kumar, Ronitt Rubinfeld. Sublinjära tidsalgoritmer // SIGACT News. - 2003. - T. 34 , nr. 4 . - S. 57-67 . - doi : 10.1145/954092.954103 .
↑ DR KN PRASANNA KUMAR, PROF BS KIRANAGI OCH PROF CS BAGEWADI. EN ALLMÄN TEORI OM SYSTEMET 'KVANTINFORMATION - KVANTINFTRÄNGNING, SUBATOMISK Partikelförfall - ASYMMETRISKA SPINSTATER, ICKE LOKALT GOLDA VARIABLER - EN KONKATENERAD MODELL // International Journal of Scientific and Research Publications. - Juli 2012. - Vol. 2 , nr. 7 . — ISSN 22503153 .
↑ Ashish V. Naik, Kenneth W. Regan, D. Sivakumar. Om kvasilinjär tidskomplexitetsteori // Teoretisk datavetenskap. — Vol. 148 . - s. 325-349 .
↑ Sedgewick, R. och Wayne K (2011). Algoritmer, 4:e upplagan Arkiverad 15 juli 2014 på Wayback Machine . sid. 186. Pearson Education, Inc.
↑ Christos H. Papadimitriou. Beräkningskomplexitet. - Reading, Mass.: Addison-Wesley, 1994. - ISBN 0-201-53082-1
↑ Alan Cobham. Proc. Logik, metodik och vetenskapsfilosofi II. - North Holland, 1965. - C. Funktioners inneboende beräkningssvårigheter.
↑ Martin Grötschel, László Lovász , Alexander Schrijver . Geometriska algoritmer och kombinatorisk optimering. - Springer, 1988. - C. Complexity, Oracles, and Numerical Computation. — ISBN 0-387-13624-X .
↑ Alexander Schrijver. Kombinatorisk optimering: polyedrar och effektivitet. - Springer, 2003. - V. 1. - C. Preliminära uppgifter om algoritmer och komplexitet. — ISBN 3-540-44389-4 .
↑ Complexity Zoo Arkiverad 26 juli 2010 på Wayback Machine Class QP: Quasipolynomial-Time Arkiverad 22 december 2015 på Wayback Machine
↑ 1 2 R. Impagliazzo, R. Paturi. Om komplexiteten i k-SAT // Journal of Computer and System Sciences. - Elsevier , 2001. - T. 62 , nr. 2 . - S. 367-375 . — ISSN 1090-2724 . doi : 10.1006 / jcss.2000.1727 .
↑ Aaronson, Scott. Ett inte helt exponentiellt dilemma. — 5 april 2009.
↑ Complexity Zoo Arkiverad 26 juli 2010 på Wayback Machine Class SUBEXP: Deterministic Subexponential-Time Arkiverad 27 augusti 2016 på Wayback Machine
↑ P. Moser. Bare's Categories on Small Complexity Classes // Lecture Notes in Computer Science . - Berlin, New York: Springer-Verlag, 2003. - S. 333-342 . — ISSN 0302-9743 .
↑ PB Miltersen. DERANDOMISERANDE KOMPLEXITETSKLASSER // Handbook of Randomized Computing. - Kluwer Academic Pub, 2001. - S. 843 .
↑ Greg Kuperberg. En subexponentiell-tidskvantalgoritm för det dihedriska dolda undergruppsproblemet // SIAM Journal on Computing. - Philadelphia: Society for Industrial and Applied Mathematics , 2005. - V. 35 , nr. 1 . - S. 188 . — ISSN 1095-7111 . - doi : 10.1137/s0097539703436345 .
↑ Oded Regev. En subexponentiell tidsalgoritm för det dihedriska dolda undergruppsproblemet med polynomrymd . – 2004.
↑ Jörg Flum, Martin Grohe. Parameteriserad komplexitetsteori. - Springer, 2006. - P. 417. - ISBN 978-3-540-29952-3 .
↑ R. Impagliazzo, R. Paturi, F. Zane. Vilka problem har starkt exponentiell komplexitet? // Tidskrift för data- och systemvetenskap . - 2001. - T. 63 , nr. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
↑ Mayr, E. & Mayer, A. Ordproblemets komplexitet för kommutativa halvgrupper och polynomideal // Adv. i matte.. - 1982. - Nummer. 46 . - S. 305-329 .
↑ JH Davenport, J. Heintz. Real Quantifier Elimination är dubbelt exponentiell // J. Symbolic Comp.. - 1988. - Vol. 5 . - S. 29-35 . .
↑ G.E. Collins. Proc. 2:a. GI Conference Automata Theory & Formal Languages. — Springer. - T. 33. - S. 134-183. — (Föreläsningsanteckningar i datavetenskap).