Algoritmin aika monimutkaisuus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17.6.2022 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Tietojenkäsittelytieteessä algoritmin aikamonimutkaisuus määritellään syötettä edustavan merkkijonon pituuden funktiona, joka on yhtä suuri kuin algoritmin käyntiaika tietyllä syötteellä [1] . Algoritmin aikamonimutkaisuus ilmaistaan yleensä suurella "O" -merkinnällä , joka ottaa huomioon vain korkeimman kertaluvun termin, eikä myöskään vakiotekijöitä eli kertoimia. Jos monimutkaisuus ilmaistaan tällä tavalla, puhutaan aikakompleksisuuden asymptoottisesta kuvauksesta, eli syötteen koon pyrkiessä äärettömyyteen. Jos esimerkiksi on olemassa luku , jonka algoritmin ajoaika ei ylitä kaikkia pituisia syötteitä , tämän algoritmin aikamonimutkaisuus voidaan arvioida asymptoottisesti muodossa . $n_{0}$ $n>n_{0}$ $5n^{3}+3n$ $O(n^{3})$

Aikamonimutkaisuus arvioidaan yleensä laskemalla algoritmin suorittamien perustoimintojen lukumäärä. Yhden tällaisen operaation suoritusaika otetaan vakiona, eli se estimoidaan asymptoottisesti muodossa . Tällaisessa merkinnässä kokonaissuoritusaika ja algoritmin suorittamien alkeisoperaatioiden lukumäärä eroavat enintään vakiokertoimella, jota ei oteta huomioon O-merkinnässä. Koska algoritmin käyntiaika voi vaihdella samankokoisilla tuloilla, käytetään yleensä huonoimman tapauksen ajoaikaa , joka on merkitty ja määritelty algoritmin pisimmäksi käyntiajaksi kaikilla syötteen pituuksilla . Harvemmin, ja tämä on yleensä määritelty erikseen, lasketaan keskimääräinen monimutkaisuus , eli kaikkien mahdollisten syötteiden käyntiajan matemaattinen odotus. Algoritmin ajoaika voidaan luokitella sen mukaan, mikä funktio on O-merkinnän alla. Esimerkiksi algoritmia, jossa on , kutsutaan algoritmiksi, jolla on lineaarinen käyntiaika , ja algoritmia, jolla on joillekin, kutsutaan polynomiksi . $O(1)$ $T(n)$ $n$ $T(n)\in O(n)$ $T(n)\in O(n^{\alpha })$ $\alpha >1$

Vaikeusaikataulu

Seuraavassa taulukossa on yhteenveto yleisimmin esiintyvistä monimutkaisuusluokista . Taulukossa , tarkoittaa mielivaltaista polynomia vuonna , eli . $poly(x)$ $x$ ${\displaystyle poly(x)=x^{O(1)))$

Nimi	Vaikeusluokka	Työtunnit, $T(n)$	Esimerkkejä työajasta	Esimerkkejä algoritmeista
vakioaika		$O(1)$	$kymmenen$	Kokonaisluvun pariteetin määrittäminen (esitetty binäärimuodossa)
käänteinen Ackermann-funktio		$O(\alpha (n))$		Poistoanalyysi operaatiota kohti disjunktijoukkojen avulla
iteroitu logaritminen aika		$O(\log ^{*}n)$		Hajautetut syklivärit
kaksinkertainen logaritminen		$O(\log \log n)$		Poistoaika toimintoa kohti käytettäessä rajoitetun prioriteetin jonoa [2]
logaritminen aika	DLOGTIME	$O(\log n)$	$\log n$ , $\log n^{2}$	Binäärihaku
polylogaritminen aika		$poly(\log n)$	$(\log n)^{2}$
sublineaarinen aika		$O(n^{c})$ klo $0<c<1$	$n^{1/2}$ , $n^{2/3}$	Hae k-ulotteisesta puusta
lineaarinen aika		$Päällä)$	$n$	Lajittelemattoman taulukon pienimmän tai suurimman elementin löytäminen
"n log-tähti n"		$O(n\log ^{*}n)$		Seidel- polygonin kolmiomittausalgoritmi [ .
lineaari-logaritminen aika		$O(n\log n)$	$n\log n$ , $\log n!$	Nopein vertailulajittelu
neliöllinen aika		$O(n^{2})$	$n^{2}$	kuplalajittelu , lisäyslajittelu , suora taitto
kuutioaika		$O(n^{3})$	$n^3$	Tavallinen kahden matriisin kertolasku. Osittaiskorrelaation laskeminen . $n\ kertaa n$
polynomiaika	P	$2^{O(\log n)}=poly(n)$	$n$ . _ $n\log n$ ${\displaystyle n^{10))$	Karmarkarin algoritmi lineaariseen ohjelmointiin , AKS-yksinkertaisuustesti
kvasipolynomiaika	QP	${\displaystyle 2^{poly(\log n)))$	${\displaystyle n^{\log \log n))$ , ${\displaystyle n^{\log n))$	Nopein tunnettu on approksimaatioalgoritmi orientoidulle Steiner-ongelmalle . $O(\log ^{2}n)$
subeksponentiaalinen aika (ensimmäinen määritelmä)	SUBEXP	$O(2^{n^{\varepsilon )))$ kaikille $\varepsilon > 0$	$2^{\log n^{\log \log n))$	Olettaen teoreettisia hypoteeseja, BPP sisältyy SUBEXP:hen. [3]
subeksponentiaalinen aika (toinen määritelmä)		$2^{o(n)}$	$2^{n^{1/3}}$	Nopeimmat tunnetut algoritmit kokonaislukujen faktorointiin ja graafisen isomorfismin tarkistamiseen
eksponentiaalinen aika (lineaarisella eksponentilla)	E	$2^{O(n)}$	$1.1^{n}$ , $10^{n}$	Matkamyyjän ongelman ratkaiseminen dynaamisella ohjelmoinnilla
eksponentiaalinen aika	EXPTIME	${\displaystyle 2^{poly(n)))$	$2^{{n}}$ , $2^{n^{2))$	Matriisin kertolaskujärjestyksen ongelman ratkaiseminen tyhjentävällä numeraatiolla
tekijäaika		$O(n!)$	$n!$	Ratkaise matkamyyjän ongelma kattavalla haulla
kaksinkertainen eksponentiaalinen aika	2-EXPTIME	$2^{2^{poly(n)))$	$2^{{2^{n}}}$	Tietyn lauseen oikeellisuuden tarkistaminen Presburger-aritmetiikassa
		${\sqrt[{n}]{\log _{n}(n)))$	1 n:lle >= 1

Vakioaika

Algoritmin sanotaan olevan vakioaikaalgoritmi (kirjoitettuna aika ), jos arvo on rajoitettu syötteen koosta riippumattomaan arvoon. Esimerkiksi yhden elementin saaminen taulukkoon vie jatkuvasti aikaa, koska sen löytämiseksi suoritetaan yksi komento . Minimiarvon löytäminen lajittelemattomasta taulukosta ei kuitenkaan ole vakioaikatoiminto, koska meidän on tarkasteltava taulukon jokaista elementtiä. Siten tämä operaatio vie lineaarista aikaa, . Jos elementtien lukumäärä tiedetään etukäteen eikä se muutu, voidaan tällaista algoritmia kutsua vakioaikaalgoritmiksi. $O(1)$ $T(n)$ $Päällä)$

Huolimatta nimestä "vakioaika", ajoajan ei tarvitse olla riippumaton tehtävän koosta, mutta suoritusajan yläraja pitäisi olla. Esimerkiksi ongelmaa "arvojen vaihtaminen ja tarvittaessa tuloksen saamiseksi " pidetään vakioajan ongelmana, vaikka algoritmin ajoaika voi riippua siitä, onko epäyhtälö jo voimassa vai ei. On kuitenkin olemassa vakio , jonka tehtävän suoritusaika ei koskaan ylitä . $a$ $b$ $a\leq b$ $a\leq b$ $t$ $t$

Alla on esimerkki jatkuvassa ajassa toimivasta koodista:

int indeksi = 5; int item = lista[indeksi]; jos (ehto on totta) sitten suorittaa joitain toimintoja jatkuvalla käyntiajalla muu suorittaa joitain toimintoja jatkuvalla käyntiajalla kun i = 1 - 100 , jos j = 1 - 200 suorittaa joitain toimintoja jatkuvalla käyntiajalla

Jos on yhtä suuri , missä on vakio, niin tämä vastaa yhtä kuin . $T(n)$ $O(\alpha )$ $\alpha$ $T(n)$ $O(1)$

Logaritminen aika

Algoritmin sanotaan ajavan logaritmisessa ajassa , jos . Koska tietokoneet käyttävät binäärilukujärjestelmää , logaritmin kanta on (eli ). Kuitenkin, kun vaihdat logaritmin kantaa ja eroavat vain vakiotekijällä , joka hylätään O-isossa merkinnässä. Näin ollen on logaritmisen aika-algoritmien standardimerkintä logaritmin kantasta riippumatta. $T(n)=O(\log n)$ $2$ $\log _{2}n$ $\log _{a}n$ $\log _{b}n$ $\log_b a$ $O(\log n)$

Logaritmisessa ajassa ajavia algoritmeja löytyy yleisesti binääripuiden operaatioista tai käytettäessä binäärihakua .

$O(\log n)$ Algoritmeja työskennelläkseen kokotietojen taulukoiden kanssa pidetään erittäin tehokkaina, koska yhden toiminnon suoritusajan suhde taulukon kokoon pienenee tätä kokoa kasvatettaessa. $n$

Hyvin yksinkertainen esimerkki tällaisesta algoritmista on sanojen etsiminen sanakirjasta. Harkitse sanakirjaa , joka sisältää sanat aakkosjärjestyksessä. Samanaikaisesti oletetaan, että kaikilla sanoilla on pituus ja että voimme käyttää mitä tahansa sanakirjan elementtiä indeksillä vakioajassa. Olkoon sanakirjan - :s elementti, niin voit tarkistaa, onko sana sanakirjassa . Harkitse tätä varten sanakirjaelementtiä , jossa tarkoittaa luvun pyöristämistä alaspäin . Jos , niin meidän pitäisi mennä taulukon oikealle puolelle, muuten - vasemmalle. Lopussa saamme ensimmäisen sanan indeksin, joka on yhtä suuri tai leksikografisesti suurempi kuin . $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 etsintä ( vektori < merkkijono > & D , merkkijono w ) { int n = D . koko (); int l = -1 , r = n ; while ( r - l > 1 ) { int m = ( l + r ) / 2 ; if ( D [ m ] < w ) { l = m ; } muu { r = m ; } } paluu r ; }

Polylogaritminen aika

Algoritmin sanotaan ajavan polylogaritmisessa ajassa , jos joillekin . Esimerkiksi matriisin kertolaskujärjestyksen ongelma voidaan ratkaista sellaisessa ajassa rinnakkaisella RAM-koneella [4] . $T(n)=O(\log ^{k}n)$ $k$

Sublineaarinen aika

Algoritmin sanotaan ajavan sublineaarisessa ajassa , jos . Tämä koskee erityisesti algoritmeja, joiden aikamonimutkaisuus on kuten edellä, sekä esimerkiksi Groverin monimutkaisuuden haun . $T(n)=o(n)$ $O(n^{{1/2}})$

Tyypillisesti algoritmit, jotka ovat tarkkoja, mutta silti ajetaan alilineaarisessa ajassa, käyttävät prosessin rinnakkaisuutta (kuten NC 1 -matriisimäärittelyalgoritmi), ei-klassisia laskelmia (kuten Groverin haussa) tai niillä on taattu arvaus syöttörakenteesta. ( binäärihakualgoritmeina ja monina puunkäsittelyalgoritmeina). Kuitenkin muodolliset kielet , kuten niiden sanojen kieli, joissa sanan ensimmäisten bittien määräämässä paikassa on 1 bitti, voivat kuitenkin olla pääteltävissä sublineaarisessa ajassa, vaikka mikä tahansa bitti voi olla tärkeä määritettäessä, kuuluuko sana johonkin kieleen. . $\log n$

Termiä alilineaarinen ajoaikaalgoritmi käytetään yleensä algoritmeista, jotka, toisin kuin yllä olevissa esimerkeissä, toimivat perinteisillä peräkkäisillä konemalleilla eivätkä vaadi syöttörakenteen a priori tuntemusta [5] . He voivat kuitenkin käyttää todennäköisyysmenetelmiä , ja usein ne on satunnaistettava minkä tahansa ei-triviaalisen ongelman varalta.

Koska tällaisen algoritmin on annettava vastaus lukematta syöttödataa kokonaan, se on hyvin riippuvainen syöttövirran sallimista pääsytavoista. Yleensä bittijonoa sisältävälle virralle oletetaan, että algoritmi voi pyytää arvoa mille tahansa . ${\displaystyle b_{1},\dots ,b_{k))$ $O(1)$ $b_{i}$ $i$

Sublineaariset aikaalgoritmit ovat yleensä todennäköisyyspohjaisia ja antavat vain likimääräisen ratkaisun. Sublineaariset ajonaikaiset algoritmit syntyvät luonnollisesti tutkittaessa ominaisuustarkistusta .

Lineaarinen aika

Algoritmin sanotaan ajavan lineaarisessa ajassa tai ajassa, jos sen monimutkaisuus on . Epämuodollisesti tämä tarkoittaa, että riittävän suurella tulokoolla käyntiaika kasvaa lineaarisesti tulon koon mukaan. Esimerkiksi prosessi, joka summaa listan kaikki elementit, vie aikaa, joka on verrannollinen luettelon pituuteen. Tämä kuvaus ei ole täysin tarkka, koska käyntiaika voi poiketa merkittävästi tarkasta suhteellisuudesta, etenkin pienillä arvoilla . $Päällä)$ $Päällä)$ $n$

Lineaarinen aika nähdään usein toivottavana algoritmin attribuuttina [6] . Paljon tutkimusta on tehty sellaisten algoritmien luomiseksi, joilla on (melkein) lineaarinen tai parempi ajoaika. Nämä tutkimukset sisälsivät sekä ohjelmisto- että laitteistolähestymistapoja. Laitteiston suorittamisen tapauksessa jotkin algoritmit, jotka matemaattisesta näkökulmasta eivät koskaan voi saavuttaa lineaarista suoritusaikaa standardeissa laskentamalleissa , voivat toimia lineaarisessa ajassa. Jotkut laitteistotekniikat käyttävät rinnakkaisuutta tämän tavoitteen saavuttamiseksi. Esimerkki on assosiatiivinen muisti . Tätä lineaarisen ajan käsitettä käytetään kuvioiden sovitusongelmissa , kuten Boyer–Moore- algoritmissa ja Ukkosen algoritmissa .

Kvasilineaarinen aika

Algoritmin sanotaan ajavan kvasilineaarisessa ajassa, jos jollakin vakiolla . Kun he puhuvat lineaari-logaritmisesta ajasta [7] . Soft-O :n suhteen tällainen ajoaika kirjoitetaan muodossa . Algoritmeille, joiden käyntiaika on lähes lineaarinen, minkä tahansa arvio on myös tosi . Siten nämä algoritmit ovat nopeampia kuin mikä tahansa polynomi , jonka aste on suurempi kuin . $T(n)=O(n\log ^{k}n)$ $k$ $k = 1$ ${\tilde {O}}(n)$ $T(n)\in o(n^{1+\varepsilon })$ $\varepsilon > 0$ $n$ $yksi$

Kvasilineaarisessa ajassa suoritettavat algoritmit edellä mainittujen lineaaristen logaritmisten algoritmien lisäksi sisältävät:

Paikalla yhdistäminen lajittelu : ; $O(n\log ^{2}n)$
Pikalajittelu : algoritmin todennäköisyyspohjaisen version käyntiajan matemaattinen odotus on missä tahansa syötteessä, deterministisessä versiossa tämä arvio on oikea vain keskimäärin kaikkien syötteiden osalta; $O(n\log n)$
Keon lajittelu , yhdistämislajittelu , introsort , binääripuulajittelu , sujuva lajittelu , pasianssilajittelu muut: pahin tapaus; $O(n\log n)$
Nopea Fourier-muunnos : ; $O(n\log n)$
Algoritmit Monge-matriiseilla : . $O(n\log n)$

Lineaarinen logaritminen aika

Lineaarinen logaritminen on kvasilineaarisen ajan erikoistapaus, jossa eksponentti on logaritmisella tekijällä. $k = 1$

Lineaari-logaritminen funktio on muodon funktio (eli lineaarisen ja logaritmisen termin tulo). Algoritmin sanotaan ajavan lineaari-logaritmisessa ajassa , jos [8] . Siten lineaarinen logaritminen funktio kasvaa nopeammin kuin lineaarinen, mutta hitaammin kuin mikä tahansa polynomi, jonka aste on suurempi kuin . $n\log n$ $T(n)=O(n\log n)$ $n$ $yksi$

Monissa tapauksissa ajoaika on yksinkertaisesti seurausta aikatoiminnon suorittamisesta käyntiajalle . Esimerkiksi lajittelu binääripuulla luo binääripuun lisäämällä siihen koon taulukon jokainen elementti yksitellen. Koska lisäystoiminto tasapainotettuun binäärihakupuuhun vie aikaa , algoritmin kokonaissuoritusaika on lineaarisesti logaritminen. $n\log n$ $n$ $O(\log n)$ $n$ $O(\log n)$

Mikä tahansa vertailupohjainen lajittelu vaatii ainakin huonoimman lineaarilogaritmisen määrän vertailuja. Yksi tämän tosiasian yksinkertaisista perusteluista informaatioteoreettisesta näkökulmasta näyttää tältä: lajittelun tuloksena saadaan pituuden permutaatio , joka määrittää yksiselitteisesti elementtien järjestyksen. Lajitteluja on kaikkiaan erilaisia, jos haluamme yksiselitteisesti koodata jokaisen niistä jollakin bittisekvenssillä, tarvitsemme keskimäärin vähintään bittiä tietoa permutaatiota kohden. Tässä tapauksessa kahden taulukkoelementin parittaisen vertailun tulos on täsmälleen yksi bitti informaatiota - joko ensimmäinen elementti on pienempi kuin toinen tai ei. Näin ollen, jos käytämme lajitteluun vain parivertailuja, taulukkoa ei ole mahdollista lajitella pahimman mahdollisen ajan kuluessa. Samanaikaisesti tällainen arvio monille rekursiivisille lajeille, kuten yhdistämislajittelulle , syntyy usein rekursiivisesta yhtälöstä . $n$ $n!$ $\log n!\sim n\log n$ $O(n\log n)$ $T(n)=T(n/2)+O(n)$

Alaneliöaika

Algoritmin sanotaan ajavan subquadraattisessa ajassa , jos . $T(n)=o(n^{2})$

Esimerkiksi vertailuihin perustuvat yksinkertaiset lajittelualgoritmit (kuten insertion sort ) ovat neliöllisiä. Samaan aikaan löytyy kehittyneempiä algoritmeja, joilla on subquadratinen ajoaika (esim. Shell sort ). Mikään yleislajittelu ei toimi lineaarisessa ajassa, mutta siirtymisellä neliö-aikaan on suuri käytännön merkitys.

Polynomiaika

Algoritmin sanotaan ajettavan polynomiajassa , jos käyntiaikaa ylhäältä rajoittaa algoritmin syötekoon polynomi , eli jollain vakiolla [1] [9] . Ongelmat , joita varten on olemassa deterministisiä polynomiaikaalgoritmeja, muodostavat kompleksisuusluokan P , joka on keskeinen laskennallisen kompleksisuusteorian kannalta . Cobhamin opinnäytetyössä todetaan, että polynomiaika on synonyymi "helposti prosessoitavaksi", "toteutettavaksi", "tehokkaaksi" tai "nopeaksi" [10] . $T(n)=O(n^{k})$ $k$

Muutamia esimerkkejä polynomialgoritmeista:

Kokonaislukupikalajittelualgoritmi suorittaa maksimitoiminnot jollekin vakiolle . Joten se toimii ja on polynomialgoritmi. $n$ $An^{2}$ $A$ $O(n^{2})$
Kaikki aritmeettiset perusoperaatiot (yhteen-, vähennys-, kerto-, jako- ja vertailu) voidaan suorittaa polynomiajassa.
Suurin yhteensopivuus kaavioissa löytyy polynomiajassa.

Tiukasti ja heikosti polynomiaika

Joissakin yhteyksissä, erityisesti optimoinnissa , erotetaan toisistaan tiukat polynomiset aika- ja heikosti polynomiset aikaalgoritmit . Nämä kaksi käsitettä koskevat vain syötteitä, jotka koostuvat kokonaisluvuista.

Tarkkaan polynomiaika on määritelty laskennan aritmeettisessa mallissa. Tässä mallissa aritmeettiset perusoperaatiot (yhteen-, vähennys-, kerto-, jako- ja vertailu) otetaan suoritusyksiköiksi operandien pituudesta riippumatta. Algoritmi toimii tiukasti polynomiajassa, jos [11]

aritmeettisen laskentamallin operaatioiden määrä on rajoitettu polynomiin syöttövirran kokonaislukujen lukumäärässä, ja
algoritmin käyttämä muisti on rajattu sisääntulon kokojen polynomilla.

Mikä tahansa algoritmi, jolla on nämä kaksi ominaisuutta, voidaan pelkistää polynomiaikaalgoritmiksi korvaamalla aritmeettiset operaatiot vastaavilla algoritmeilla aritmeettisten operaatioiden suorittamiseksi Turingin koneella . Jos toinen yllä olevista vaatimuksista ei täyty, tämä ei enää pidä paikkaansa. Annettu kokonaisluku (joka vie Turingin koneessa n:ään verrannollisen muistin), se voidaan laskea n:ssä operaatiossa käyttämällä toistuvaa eksponentiota . Edustamiseen käytetty muisti on kuitenkin verrannollinen arvoon , ja se riippuu eksponentiaalisesti eikä polynomiaalisesti syötteeseen käytetystä muistista. Siksi - on mahdotonta suorittaa näitä laskelmia polynomiajassa Turingin koneella, mutta se voidaan suorittaa polynomisella määrällä aritmeettisia operaatioita. $2^{n}$ $2^{{2^{n}}}$ $2^{{2^{n}}}$ $2^{n}$

Sitä vastoin on olemassa algoritmeja, jotka toimivat Turingin koneen vaiheiden lukumäärässä, joita rajoittaa binäärikoodatun syötteen polynomipituus, mutta eivät toimi aritmeettisten operaatioiden lukumäärässä, joita rajoittaa lukujen lukumäärän polynomi. syöttö. Euklidesin algoritmi kahden kokonaisluvun suurimman yhteisen jakajan laskemiseksi on yksi esimerkki. Kahdelle kokonaisluvulle ja algoritmin ajoaika on rajoitettu Turingin koneen askeleilla. Tämä luku on polynomi, jonka koko on lukujen ja binääriesitys , joka voidaan esittää karkeasti muodossa . Samaan aikaan aritmeettisten operaatioiden määrää ei voi rajoittaa syötteen kokonaislukujen määrällä (joka tässä tapauksessa on vakio - syötteessä on vain kaksi numeroa). Tämän huomautuksen valossa algoritmi ei toimi tiukasti polynomisessa ajassa. Algoritmin todellinen ajoaika riippuu arvoista ja , eikä vain syötteessä olevien kokonaislukujen määrästä. $a$ $b$ $O((\log \ a+\log \ b)^{2})$ $a$ $b$ $\log \a+\log\b$ $a$ $b$

Jos algoritmi kulkee polynomiajassa, mutta ei tiukasti polynomiajassa, sen sanotaan ajavan heikosti polynomiajassa [12] . Lineaarinen ohjelmointi on hyvin tunnettu esimerkki ongelmasta, jolle tunnetaan heikosti polynomialgoritmi, mutta ei tiukasti polynomista algoritmia . Heikosti polynomiaikaa ei pidä sekoittaa pseudopolynomiaikaan .

Vaikeusluokat

Polynomiajan käsite johtaa useisiin monimutkaisuusluokkiin laskennallisessa monimutkaisuusteoriassa. Alla on lueteltu joitakin tärkeitä polynomiajan avulla määritettyjä luokkia.

P : Deterministisellä Turingin koneella polynomiajassaratkaistavien ratkottavuusongelmien kompleksisuusluokka .
NP : Ratkaisuongelmien monimutkaisuusluokka, jotka voidaan ratkaista epädeterministisellä Turingin koneella polynomiajassa.
ZPP : Ratkaisuongelmien monimutkaisuusluokka, joka voidaan ratkaista nollavirheellä todennäköisyyspohjaisessa Turingin koneessa polynomiajassa.
RP : Ratkaisuongelmien monimutkaisuusluokka, jotka voidaan ratkaista yksipuolisilla virheillä todennäköisyyspohjaisessa Turingin koneessa polynomiajassa.
BPP : Ratkaisuongelmien monimutkaisuusluokka, joka voidaan ratkaista kaksipuolisilla virheillä todennäköisyyspohjaisessa Turingin koneessa polynomiajassa.
BQP : Ratkaisuongelmien monimutkaisuusluokka, joka voidaan ratkaista kaksipuolisilla virheillä kvantti Turingin koneessa polynomiajassa.

P on pienin aikamonimutkaisuusluokka deterministisellä koneella, joka on vakaa konemallin kannalta. (Esimerkiksi siirtyminen yksinauhaisesta Turingin koneesta moninauhaiseen Turingin koneeseen saattaa johtaa neliölliseen nopeuteen, mutta mikä tahansa algoritmi, joka toimii polynomiajassa yhdessä mallissa, toimii polynomiajassa toisessa.)

Superpolynomiaika

Algoritmin sanotaan ajavan superpolynomiajassa , jos T ( n ) ei rajoita ylhäältä polynomilla. Tämä aika on ω( n c ) kaikille vakioille c , missä n on syöteargumentti, yleensä tulobittien lukumäärä.

Esimerkiksi algoritmi, joka ottaa 2n askelta, vaatii superpolynomiajan (tarkemmin eksponentiaalisen ajan) syötteelle, jonka koko on n .

On selvää, että eksponentiaalisia resursseja käyttävä algoritmi on superpolynomi, mutta jotkut algoritmit ovat erittäin heikosti superpolynomia. Esimerkiksi Adleman-Pomerance-Rumeli primiteettitesti suoritetaan n O(log log n ) -ajassa n - bittisellä tulolla. Tämä kasvaa nopeammin kuin mikään polynomi riittävän suurella n :llä , mutta syötteen koon tulee olla erittäin suuri, jotta sitä ei hallitse pieniasteinen polynomi.

Superpolynomiaikaa vaativa algoritmi on kompleksisuusluokan P ulkopuolella . Cobhamin opinnäytetyössä todetaan, että nämä algoritmit ovat epäkäytännöllisiä, ja monissa tapauksissa ne ovatkin. Koska luokkien P ja NP yhtäläisyysongelmaa ei ole ratkaistu, ei tällä hetkellä tunneta algoritmeja NP-täydellisten ongelmien ratkaisemiseksi polynomiajassa.

Kvasipolynomiaika

Kvasipolynomiaikaiset algoritmit ovat algoritmeja, jotka toimivat hitaammin kuin polynomiaika, mutta eivät yhtä hitaita kuin eksponentiaaliset aikaalgoritmit. Kvasipolynomialgoritmin pahimman tapauksen ajoaika on yhtä suuri jollekin kiinteälle c :lle . Tunnettu klassinen algoritmi kokonaisluvun faktorointiin, yleinen lukukenttäseulamenetelmä , joka kulkee suunnilleen ajassa , ei ole kvasipolynomi, koska ajoaikaa ei voida esittää kuten jollekin kiinteälle c :lle . Jos kvasipolynomisen aika-algoritmin määritelmässä vakio "c" on 1, saadaan polynomiaikaalgoritmi, ja jos se on pienempi kuin 1, saadaan alilineaarinen aika-algoritmi. ${\displaystyle 2^{O((\log n)^{c)))))$ ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O((\log n)^{c)))))$

Kvasipolynomiaikaiset algoritmit syntyvät yleensä pelkistettäessä NP-kova ongelma toiseksi ongelmaksi. Voit esimerkiksi ottaa NP-kovan ongelman, esimerkiksi 3SAT , ja pelkistää sen toiseksi ongelmaksi B, mutta ongelman koko tulee . Tässä tapauksessa pelkistys ei todista, että ongelma B on NP-kova, tällainen pelkistys osoittaa vain, että B:lle ei ole polynomialgoritmia, ellei ole olemassa kvasipolynomialgoritmia 3SAT:lle (ja sitten kaikille NP -ongelmille) . Samoin on joitakin ongelmia, joille tunnemme kvasipolynomiajan algoritmeja, mutta joiden osalta polynomiajan algoritmeja ei tunneta. Tällaisia ongelmia esiintyy approksimaatioalgoritmeissa. Kuuluisa esimerkki on orientoitu Steiner-ongelma , jolle on olemassa likimääräinen kvasipolynomialgoritmi approksimaatiokertoimella (jossa n on kärkien lukumäärä), mutta polynomiaikaisen algoritmin olemassaolo on avoin ongelma. ${\displaystyle 2^{O((\log n)^{c)))))$ $O(\log ^{3}n)$

Monimutkaisuusluokka QP koostuu kaikista ongelmista, joilla on kvasipolynomisia aikaalgoritmeja. Se voidaan määritellä DTIME :na seuraavasti [13] :

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

Suhde NP-täydellisiin ongelmiin

Monimutkaisuusteoriassa luokkien P ja NP yhtäläisyyden ratkaisematon ongelma kysyy, onko kaikilla luokan NP ongelmilla polynomiaikaisia ratkaisualgoritmeja. Kaikilla tunnetuilla NP-täydellisten ongelmien algoritmeilla, kuten 3SAT:lla, on eksponentiaalinen aika. Lisäksi oletetaan, että monille luonnollisille NP-täydellisille ongelmille ei ole algoritmeja, joilla on subeksponentiaalinen suoritusaika. Tässä "subeksponentiaalinen aika" on otettu alla olevan toisen määritelmän merkityksessä. (Toisaalta monet graafisen teorian ongelmat, joita luonnollisesti edustavat vierekkäisyysmatriisit, ovat ratkaistavissa subeksponentiaalisessa ajassa yksinkertaisesti siksi, että syötteen koko on pisteiden lukumäärän neliö.) Tämä olettamus (k-SAT-ongelmalle) tunnetaan ns. eksponentiaalinen aika-arvaus [14] . Koska se olettaa, että NP-täydellisillä ongelmilla ei ole kvasipolynomisia aikaalgoritmeja, jotkin ei-approksimaatiotulokset approksimaatioalgoritmien alalla olettavat , että NP-täydellisillä ongelmilla ei ole kvasipolynomiaikaisia algoritmeja. Katso esimerkiksi hyvin tunnetut tulokset joukon peittoongelman ei-lähestyttävyydestä .

Subeksponentiaalinen aika

Termiä subeksponentiaalinen time käytetään ilmaisemaan, että jonkin algoritmin suoritusaika voi kasvaa nopeammin kuin minkä tahansa polynomin, mutta jää olennaisesti eksponentiaalista lyhyemmäksi. Tässä mielessä ongelmat, joissa on subeksponentiaalisen ajan algoritmit, ovat muokattavampia kuin algoritmit, joissa on vain eksponentiaalinen aika. "Subeksponentiaalisen" tarkkaa määritelmää ei ole vielä yleisesti hyväksytty [15] , ja annamme alla kaksi yleisintä määritelmää.

Ensimmäinen määritelmä

Tehtävän sanotaan ratkeavan subeksponentiaalisessa ajassa, jos se ratkaistaan algoritmilla, jonka ajoajan logaritmi kasvaa vähemmän kuin mikä tahansa polynomi. Tarkemmin sanottuna ongelmalla on subeksponentiaalinen aika, jos mille tahansa ε > 0:lle on olemassa algoritmi, joka ratkaisee ongelman O(2 n ε ) ajassa. Kaikkien tällaisten ongelmien joukko muodostaa kompleksisuusluokan SUBEXP , joka voidaan ilmaista DTIME- arvona [3] [16] [17] [18] .

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

Huomaa, että tässä ε ei ole osa syöttödataa, ja jokaisella e:llä voi olla oma algoritminsa ongelman ratkaisemiseksi.

Toinen määritelmä

Jotkut kirjoittajat määrittelevät subeksponentiaalisen ajan kulkuajaksi 2 o( n ) [14] [19] [20] . Tämä määritelmä mahdollistaa pidemmän käyttöajan kuin ensimmäinen määritelmä. Esimerkki tällaisesta osaeksponentiaalisesta aikaalgoritmista on hyvin tunnettu klassinen kokonaislukujen laskentaalgoritmi, yleinen lukukenttäseulamenetelmä , joka kulkee noin ajassa , jossa syötepituus on n . Toinen esimerkki on hyvin tunnettu graafin isomorfismiongelman algoritmi , jonka suoritusaika on . ${\displaystyle 2^{{\tilde {O}}(n^{1/3}})))$ ${\displaystyle 2^{O({\sqrt {n\log n))))$

Huomaa, että on ero, onko algoritmi subeksponentiaalinen kärkipisteiden vai reunojen lukumäärässä. Parametrisoidussa kompleksisuudessa tämä ero esiintyy eksplisiittisesti määrittämällä pari , ratkaistavuusongelma ja parametri k . SUBEPT on kaikkien parametroitujen ongelmien luokka, jotka suoritetaan osaeksponentiaalisessa ajassa k :ssa ja polynomiajassa n :ssä [21] : ${\näyttötyyli (L,k)}$

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

Tarkemmin sanottuna SUBEPT on kaikkien parametroitujen ongelmien luokka, joille on laskettava funktio c ja algoritmi, joka ratkaisee L :n ajassa . ${\näyttötyyli (L,k)}$ $f:\mathbb {N} \to \mathbb {N}$ $f\in o(k)$ $2^{f(k)}\cdot {\text{poly}}(n)$

Eksponentiaalinen aika-oletus

Eksponentiaalinen aikaoletus (' ETH ) toteaa, että 3SAT , konjunktiivisen normaalimuodon Boolen kaavojen tyydyttävyysongelma, jossa on enintään kolme literaalia lausetta kohti ja n muuttujaa, ei voida ratkaista ajassa 2o ( n ) . Tarkemmin sanottuna olettamus sanoo, että on olemassa jokin vakio c >0, jota 3SAT ei voida ratkaista 2 cn :ssä millään deterministisellä Turingin koneella. Jos m on lauseiden lukumäärä, ETH vastaa hypoteesia, jonka mukaan k -SAT ei voida ratkaista ajassa 2 o ( m ) millekään kokonaisluvulle k ≥ 3 [22] . Eksponentiaalisesta aikahypoteesista seuraa, että P ≠ NP .

Eksponentiaalinen aika

Algoritmin sanotaan ajavan eksponentiaalisessa ajassa , jos T ( n ) on yläpuolella 2 poly( n ) :n rajana , missä poly( n ) on jokin polynomi luvussa n . Muodollisemmin algoritmi toimii eksponentiaalisessa ajassa, jos T ( n ) on rajoitettu O( 2n k ) johonkin vakioon k . Tehtävät, jotka suoritetaan eksponentiaalisessa ajassa deterministisellä Turingin koneella, muodostavat EXP -kompleksisuusluokan .

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

Joskus termiä eksponentiaalinen aika käytetään algoritmeille, joille T ( n ) = 2 O( n ) , jolloin eksponentti on korkeintaan n: n lineaarinen funktio . Tämä johtaa monimutkaisuusluokkaan E .

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

Kaksinkertainen eksponentiaalinen aika

Algoritmin sanotaan ajavan kaksinkertaisesti eksponentiaalisessa -ajassa, jos T ( n ) on yläpuolella 2 2 poly( n ) -raja, missä poly( n ) on jokin polynomi luvussa n . Tällaiset algoritmit kuuluvat 2-EXPTIME kompleksisuusluokkaan .

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

Tunnettuja kaksinkertaisesti eksponentiaalisia algoritmeja ovat mm.

Laskentamenettely Presburger-aritmetiikkaa varten
Gröbnerin perusteen laskeminen (pahin tapaus [23] )
Kvantoijien eliminointi todellisissa suljetuissa kentissä vaatii vähintään kaksi kertaa eksponentiaalisen ajoajan [24] ja se voidaan tehdä tässä ajassa [25] .

Katso myös

L-merkintä
Muistin vaikeus

Muistiinpanot

↑ 12 Michael Sipser . Johdatus laskentateoriaan. - Course Technology Inc, 2006. - ISBN 0-619-21764-2 .
↑ Kurt Mehlhorn, Stefan Naher. Rajoitetut järjestetyt sanakirjat O(log log N) ajassa ja O(n) avaruudessa // 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:llä on subeksponentiaalisia aikasimulaatioita, ellei EXPTIMElla ole julkaistavia todisteita // Computational Complexity. - Berliini, New York: Springer-Verlag , 1993. - Vol. 3 , no. 4 . - S. 307-318 . - doi : 10.1007/BF01275486 .
↑ JE Rawlins, Gregory E. Shannon. Tehokas matriisiketjujärjestys polylogiajassa // SIAM Journal on Computing. - Philadelphia: Society for Industrial and Applied Mathematics , 1998. - V. 27 , no. 2 . - S. 466-490 . — ISSN 1095-7111 . - doi : 10.1137/S0097539794270698 .
↑ Ravi Kumar, Ronitt Rubinfeld. Sublineaariset aikaalgoritmit // SIGACT News. - 2003. - T. 34 , no. 4 . - S. 57-67 . - doi : 10.1145/954092.954103 .
↑ DR KN PRASANNA KUMAR, PROF BS KIRANAGI JA PROF CS BAGEWADI. JÄRJESTELMÄN YLEINEN TEORIA KVANTTITIEDOT - KVANTTILEIKKUMINEN, SUBATOMINEN HIUKSEN HAJOAMINEN - ASYMMETRISET SPIN-TILAT, EI-PAIKALLISESSA PIILOTTEET MUUTTUJAT - YHTEYDETTY MALLI // International Journal of Scientific and Research Publications. - Heinäkuu 2012. - Osa 2 , no. 7 . — ISSN 22503153 .
↑ Ashish V. Naik, Kenneth W. Regan, D. Sivakumar. Kvasilineaarisesta ajan monimutkaisuusteoriasta // Teoreettinen tietojenkäsittelytiede. — Voi. 148 . - s. 325-349 .
↑ Sedgewick, R. ja Wayne K (2011). Algorithms, 4. painos Arkistoitu 15. heinäkuuta 2014 the Wayback Machine . s. 186. Pearson Education, Inc.
↑ Christos H. Papadimitriou. Laskennallinen monimutkaisuus. - Reading, Mass.: Addison-Wesley, 1994. - ISBN 0-201-53082-1 .
↑ Alan Cobham. Proc. Logiikka, metodologia ja tiedefilosofia II. - North Holland, 1965. - C. Funktioiden luontainen laskennallinen vaikeus.
↑ Martin Grötschel, László Lovász , Alexander Schrijver . Geometriset algoritmit ja kombinatorinen optimointi. - Springer, 1988. - C. Monimutkaisuus, Oraakkelit ja numeerinen laskenta. — ISBN 0-387-13624-X .
↑ Alexander Schrijver. Kombinatorinen optimointi: Polyhedra ja tehokkuus. - Springer, 2003. - V. 1. - C. Alkuperäiset algoritmit ja monimutkaisuus. — ISBN 3-540-44389-4 .
↑ Complexity Zoo arkistoitu 26. heinäkuuta 2010 Wayback Machine Class QP:ssä: Quasipolynomial-Time Arkistoitu 22. joulukuuta 2015 Wayback Machinessa
↑ 1 2 R. Impagliazzo, R. Paturi. K-SAT:n monimutkaisuudesta // 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. Ei aivan eksponentiaalinen dilemma. – 5. huhtikuuta 2009.
↑ Complexity Zoo Arkistoitu 26. heinäkuuta 2010 Wayback Machine -luokkaan SUBEXP: Deterministic Subexponential-Time Arkistoitu 27. elokuuta 2016 Wayback Machinessa
↑ P. Moser. Baren luokat pienistä monimutkaisuusluokista // Tietojenkäsittelytieteen luentomuistiinpanot . - Berliini, New York: Springer-Verlag, 2003. - S. 333-342 . — ISSN 0302-9743 .
↑ PB Miltersen. DERANDOMIZING COMPLEXITY CLASSES // Handbook of Randomized Computing. - Kluwer Academic Pub, 2001. - S. 843 .
↑ Greg Kuperberg. Subeksponentiaalinen aika-kvanttialgoritmi dihedraalisen piilotetun alaryhmän ongelmalle // SIAM Journal on Computing. - Philadelphia: Society for Industrial and Applied Mathematics , 2005. - V. 35 , no. 1 . - S. 188 . — ISSN 1095-7111 . - doi : 10.1137/s0097539703436345 .
↑ Oded Regev. Subeksponentiaalinen aikaalgoritmi dihedraalisen piilotetun alaryhmän ongelmalle polynomiavaruuden kanssa . – 2004.
↑ Jörg Flum, Martin Grohe. Parametrisoitu kompleksiteoria. - Springer, 2006. - S. 417. - ISBN 978-3-540-29952-3 .
↑ R. Impagliazzo, R. Paturi, F. Zane. Mitkä ongelmat ovat voimakkaasti eksponentiaalisia? // Journal of Computer and System Sciences . - 2001. - T. 63 , no. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
↑ Mayr, E. & Mayer, A. Sanaongelman monimutkaisuus kommutatiivisille puoliryhmille ja polynomiideaaleille // Adv. matematiikassa.. - 1982. - Numero. 46 . - S. 305-329 .
↑ JH Davenport, J. Heintz. Todellinen kvantitorin eliminaatio on kaksinkertaisesti eksponentiaalinen // J. Symbolic Comp.. - 1988. - Voi. 5 . - S. 29-35 . .
↑ G.E. Collins. Proc. 2. GI-konferenssiautomaattien teoria ja muodolliset kielet. - Springer. - T. 33. - S. 134-183. — (Luentomuistiinpanot tietojenkäsittelytieteestä).