Wiki definierar Polynomtid som brak:
En algoritm sägs ha polynomtid om dess körtid är övre begränsad av ett polynomuttryck i storleken på ingången för algoritmen, dvs $ T (n) = O (n ^ k) $ för någon konstant $ k $
I förstå att i allmänhet skillnaden mellan Polynomtid och Exponentiell tid är att den exponentiella funktionen växer strikt snabbare än någon polynomfunktion, asymptotiskt ( referens ).
Jag försöker förstå kärnan definition av Exponentiell tid .
- Vilka element får en algoritm att köras i Exponentiell tid ?
- Vilken förändring måste jag göra i polynomuttryck att göra det Exponentiell tid ? (Av it Jag hänvisar till algoritmdefinitionen i början av frågan)
Kommentarer
- 1. Gör exponentiellt många saker. 2. Använd polynom som kraften i en bas > 1.
- Jag förstår inte ' fråga. Polynom är polynom; exponentials är exponentials. Att fråga vad du behöver ändra för att göra ett polynom till ett exponentiellt är som att fråga vad du behöver ändra för att göra en logaritm till ett cosinus.
- @ DavidRicherby Kommer det att finnas exponentiella tidsfunktioner om P = NP? Hur kan du definiera en exponentiell tidsfunktion i termer av polynomuttryck?
- Exponentiella funktioner kommer säkert fortfarande att finnas om P = NP. Det finns förmodligen fortfarande problem som ' tar exponentiell tid även om P = NP, men ingen kommer att tänka omedelbart. En exponentiell funktion kan definieras i termer av ett polynom, men det polynom måste vara oändligt långt – du kanske vill slå upp Taylor Expansions om du ' är intresserad av detta.
- @ymbirtt Även den enklaste versionen av tidshierarkiteksten säger att det inte finns någon polynom-tidsalgoritm för något EXPTIME-komplett problem. Att ' är ett ovillkorligt resultat: det beror inte ' på antagandet att P $ \ neq $ NP.
Svar
-
Det finns inget enkelt svar för det här, men det finns tecken att se upp för Att undersöka alla möjliga delmängder av en uppsättning är till exempel exponentiell – så om jag hade en uppsättning heltal $ \ {x_1, …, x_n \} $ och ville kontrollera varje delmängd av dessa för att se om de sammanfattar till $ 0 $, måste jag överväga exakt $ 2 ^ n $ delmängder, vilket gör denna metod exponentiell tid. Flera olika fällor kan göra en algoritm exponentiell tid, men i stället för att leta efter breda kategorier, analysera algoritmer från fall till fall.
-
Om en algoritm tar $ n ^ 2 $ steg för att slutföra är det polynom. Om det tar $ 2 ^ n $ steg är det exponentiellt. Skillnaden är positionen för $ n $. Om något är $ O (n ^ m) $ för $ n > 1 $, $ m > 0 $, då är det polynom i $ n $ för fast $ m $, men exponentiellt i $ m $ för fast $ n $.
Kommentarer
- Var försiktig. Funktionen $ n ^ m $ isn ' t polynom i $ n $ såvida inte $ m $ är en konstant. Och om $ m $ är en konstant, det betyder inte ' att säga att funktionen är exponentiell i den konstanten.
- Ja, du ' är rätt. Jag ' Jag klargör det.
Svar
Ofta får du en exponentiell tidsbrute-kraftalgoritm när du tänker på ett problem och räknar upp hela sökutrymmet. Vanligtvis skulle du tänka på delmängdsproblem (i SAT skulle du välja en delmängd av variabler satt till true), permutationsproblem (i TSP är varje turné en permutation av städerna) och partitionsproblem (i diagramfärgning försöker du p gruppera hörn i färgklasser). Eller överväg att sortera jämnt: det finns $ n! $ Permutationer på $ n $ heltal. Gå igenom varje permutation och kontrollera om den är sorterad. Dumt (och långsamt), men det fungerar.
Kommentarer
- Men notera att $ O (n!) $ Är ännu värre än $ O ( k ^ n) $. Om du ' fortfarande försöker lära dig om tidskomplexitet kan det vara en bra sak att bevisa för dig själv.