Wiki definerer Polynomtid som brakk:
En algoritme sies å være av polynomisk tid hvis kjøretiden er øvre avgrenset av et polynomuttrykk i størrelsen på inngangen for algoritmen, dvs. $ T (n) = O (n ^ k) $ for noen konstant $ k $
I forstå at generelt sett er forskjellen mellom Polynomisk tid og Eksponentiell tid er at eksponentiell funksjon vokser strengt raskere enn noen polynomfunksjon, asymptotisk ( referanse ).
Jeg prøver å forstå kjernen definisjon av Eksponentiell tid .
- Hvilke elementer vil få en algoritme til å kjøre i Eksponentiell tid ?
- Hvilken endring må jeg gjøre i polynomeuttrykk for å gjøre det til Eksponentiell tid ? (Av it Jeg refererer til algoritmedefinisjonen i begynnelsen av spørsmålet)
Kommentarer
- 1. Gjør eksponentielt mange ting. 2. Bruk polynomet som kraften til en base > 1.
- Jeg forstår ikke ' for å forstå ditt andre spørsmål. Polynomer er polynomer; eksponentiell er eksponentiell. Å spørre hva du trenger å endre for å gjøre et polynom til et eksponentielt, er som å spørre hva du trenger å endre for å lage en logaritme til et cosinus.
- @ DavidRicherby Vil det være eksponentielle tidsfunksjoner hvis P = NP? Hvordan kan du definere en eksponentiell tidsfunksjon i form av polynomisk uttrykk?
- Eksponensielle funksjoner vil absolutt fortsatt eksistere hvis P = NP. Det er sannsynligvis fremdeles problemer som ' tar eksponentiell tid, selv om P = NP, men ingen kommer til å tenke umiddelbart. En eksponentiell funksjon kan defineres i form av et polynom, men det polynomet må være uendelig langt – det kan være lurt å slå opp Taylor Expansions hvis du ' er interessert i dette.
- @ymbirtt Selv den enkleste versjonen av tidshierarki teorem sier at det ikke er noen polynom-tidsalgoritme for noe EXPTIME-komplett problem. At ' er et ubetinget resultat: det avhenger ikke ' av antagelsen om at P $ \ neq $ NP.
Svar
-
Det er ikke noe lett svar på denne, selv om det er tegn å se etter Å undersøke alle mulige delsett av et sett, for eksempel, er eksponentiell – så hvis jeg hadde et sett med heltall $ \ {x_1, …, x_n \} $, og ønsket å sjekke hvert delsett av disse for å se om de summerer til $ 0 $, må jeg vurdere nøyaktig $ 2 ^ n $ delmengder, noe som gjør denne metoden eksponentiell tid. Flere forskjellige feller kan gjøre en algoritme eksponentiell tid, men i stedet for å se etter brede kategorier, kan du analysere algoritmer fra sak til sak.
-
Hvis en algoritme tar $ n ^ 2 $ trinn for å fullføre, er den polynom. Hvis det tar $ 2 ^ n $ trinn, er den eksponentiell. Forskjellen er posisjonen til $ n $. Hvis noe er $ O (n ^ m) $ for $ n > 1 $, $ m > 0 $, så er det «s polynom i $ n $ for faste $ m $, men eksponentielt i $ m $ for faste $ n $.
Kommentarer
- Forsiktig. Funksjonen $ n ^ m $ isn ' t polynom i $ n $ med mindre $ m $ er en konstant. Og hvis $ m $ er en konstant, betyr det ikke ' t å si at funksjonen er eksponentiell i den konstante.
- Ja, du ' har rett. Jeg ' vil avklare det.
Svar
Ofte får du en eksponentiell tidsbrute-force-algoritme når du vurderer et problem, og teller opp hele søkeområdet. Vanligvis tenker du på delsettproblemer (i SAT velger du et delsett av variabler satt til sant), permutasjonsproblemer (i TSP er hver tur en permutasjon av byene) og partisjonsproblemer (i graffarging prøver du å p oppdel hjørnene i fargeklasser). Eller vurder å sortere til og med: det er $ n! $ Permutasjoner på $ n $ heltall. Gå gjennom hver permutasjon, og sjekk om den er sortert. Dumt (og tregt), men det fungerer.
Kommentarer
- Selv om det er oppmerksom på at $ O (n!) $ Er enda verre enn $ O ( k ^ n) $. Hvis du ' fortsatt prøver å lære om tidskompleksitet, kan dette være en nyttig ting å bevise for deg selv.