Wiki määrittelee Polynomiajan kesannoksi:
Algoritmin sanotaan olevan polynomi-aikaa, jos sen käyntiaikaa rajoittaa ylempi polynomilauseke algoritmin syötteen koko, eli $ T (n) = O (n ^ k) $ joillekin vakioille $ k $
I ymmärrä, että yleisesti ottaen ero polynomiaika ja eksponentiaalinen aika on, että eksponentiaalifunktio kasvaa ehdottomasti nopeammin kuin mikään polynomifunktio asymptoottisesti ( viite ).
Yritän ymmärtää ydintä määritelmä Eksponentiaalinen aika .
- Mitkä elementit saavat yhden algoritmin toimimaan Eksponentiaalinen aika ?
- Mitä muutoksia minun on tehtävä -polynomilausekkeessa tehdäksesi siitä Eksponentiaalinen aika ? ( it viittaan algoritmin määritelmään alussa kysymyksestä)
Kommentit
- 1. Tee eksponentiaalisesti monia asioita. 2. Käytä polynomia tukiaseman voimana. > 1.
- En ymmärrä sekuntiasi ' kysymys. Polynomit ovat polynomeja; eksponentiaalit ovat eksponentiaalisia. Kysymys siitä, mitä sinun on muutettava, jotta polynomista tulisi eksponentiaalinen, on kuin kysymys siitä, mitä sinun on muutettava, jotta logaritmista saadaan kosini.
- @DavidRicherby Onko eksponentiaalisia aikatoimintoja, jos P = NP? Kuinka voit määrittää eksponentiaalisen aikafunktion polynomilausekkeella?
- Eksponentiaalisia funktioita on varmasti edelleen olemassa, jos P = NP. On todennäköisesti vielä ongelmia, jotka ' vievät eksponentiaalista aikaa, vaikka P = NP, vaikka mikään ei tule mieleen heti. Eksponentiaalinen funktio voidaan määrittää polynomina, mutta polynomin on oltava äärettömän pitkä – voit etsiä Taylor-laajennuksia, jos ' kiinnostaa tätä.
- @ymbirtt Jopa aikahierarkialauseen helpoin versio sanoo, ettei EXPTIME-complete -ongelmalle ole olemassa polynomi-aika-algoritmia. Että ' on ehdoton tulos: se ei ' ole riippuvainen oletuksesta, että P $ \ neq $ NP.
Vastaus
-
Tähän ei ole helppoa vastausta, vaikka onkin merkkejä, joihin kannattaa varoa Esimerkiksi joukon kaikkien mahdollisten osajoukkojen tutkiminen on eksponentiaalista – joten jos minulla olisi joukko kokonaislukuja $ \ {x_1, …, x_n \} $, ja halusin tarkistaa näiden jokaisen osajoukon nähdäksesi summaavatko ne arvoon $ 0 $, minun on harkittava tarkalleen $ 2 ^ n $ alijoukkoa, mikä tekee tästä menetelmästä eksponentiaalisen ajan. Useat erilaiset ansat voivat tehdä algoritmista eksponentiaalisen ajan, mutta analysoi algoritmeja tapauskohtaisesti sen sijaan, että etsittäisi laajoja luokkia.
-
Jos algoritmi vie $ n ^ 2 $ vaihetta loppuun, se on polynomi. Jos se vie $ 2 ^ n $ askelta, se on eksponentiaalinen. Ero on $ n $: n sijainti. Jos jokin on $ O (n ^ m) $ hintaan $ n > 1 $, $ m > 0 $, niin se ”s polynomi $ n $: ssa kiinteälle $ m $: lle, mutta eksponentti $ m $: lle kiinteälle $ n $: lle.
Kommentit
- Varovainen. Funktio $ n ^ m $ ei ole ' t polynomi luvussa $ n $, ellei $ m $ ole vakio. Ja jos $ m $ on vakio, ei ole ' järkevää sanoa, että funktio on eksponentiaalinen kyseisessä vakiossa.
- Kyllä, sinä ' on oikeassa. Olen ' ll selventää sitä.
Vastaa
Saat usein eksponentiaalisen aika-raaan voiman algoritmin, kun tarkastelet ongelmaa ja luetat sen koko hakutilan. Tyypillisesti luulet osajoukkoongelmia (SAT: ssa valitsisit osajoukon muuttujat ovat tosi), permutaatio-ongelmat (TSP: ssä jokainen kierros on kaupunkien permutaatio) ja osio-ongelmat (kuvaajan värityksessä yrität pisteiden jakaminen väriluokkiin). Tai harkitse jopa lajittelua: $ n! $-Kokonaislukuja on $ n! $ -Muunnoksia. Käy läpi kaikki permutaatiot ja tarkista, onko ne lajiteltu. Hölmö (ja hidas), mutta se toimii.
Kommentit
- Huomaa kuitenkin, että $ O (n!) $ On jopa huonompi kuin $ O ( k ^ n) $. Jos ' yrität edelleen oppia ajan monimutkaisuudesta, tämä voi olla hyödyllinen asia todistaa itsellesi.