Wiki definuje polynomiální čas jako ladem:
O algoritmu se říká, že má polynomiální čas, pokud je jeho doba běhu horní hranicí polynomiálního výrazu v velikost vstupu pro algoritmus, tj. $ T (n) = O (n ^ k) $ pro nějakou konstantu $ k $
I pochopte, že obecně platí rozdíl mezi polynomiálním časem a exponenciálním časem je, že exponenciální funkce roste striktně rychleji než jakákoli polynomiální funkce, asymptoticky ( reference ).
Snažím se porozumět jádru definice exponenciálního času .
- Z jakých prvků bude v exponenciální čas ?
- Jakou změnu musím provést v polynomiálním výrazu aby to bylo exponenciální čas ? ( it mám na mysli definici algoritmu na začátku otázky)
Komentáře
- 1. Dělejte exponenciálně mnoho věcí. 2. Použijte polynom jako sílu základny > 1.
- Nerozumím vašemu druhému ' otázka. Polynomy jsou polynomy; exponenciály jsou exponenciály. Zeptat se, co musíte změnit, aby se polynom stal exponenciálním, je jako zeptat se, co musíte změnit, aby se logaritmus stal kosinusem.
- @DavidRicherby Budou existovat exponenciální časové funkce, pokud P = NP? Jak můžete definovat exponenciální časovou funkci z hlediska polynomiálního výrazu?
- Exponenciální funkce určitě budou existovat, pokud P = NP. Pravděpodobně stále přetrvávají problémy, které ' ll trvají exponenciálně, i když je P = NP, ačkoli žádný z nich mi okamžitě nevypadá. Exponenciální funkci lze definovat pomocí polynomu, ale tento polynom musí být nekonečně dlouhý – možná vás bude chtít vyhledat Taylor Expansions, pokud vás ' zajímá.
- @ymbirtt I ta nejjednodušší verze věty o časové hierarchii říká, že pro žádný problém EXPTIME není k dispozici žádný algoritmus polynomiálního času. To ' je bezpodmínečný výsledek: nezáleží ' na předpokladu, že P $ \ neq $ NP.
Odpověď
-
Na tuto otázku není snadná odpověď, i když existují známky, na které je třeba dávat pozor . Zkoumání každé možné podmnožiny množiny je například exponenciální – takže kdybych měl množinu celých čísel $ \ {x_1, …, x_n \} $, a chtěl bych zkontrolovat každou jejich podmnožinu, abych zjistil, zda se sčítají až $ 0 $, musím zvážit přesně $ 2 ^ n $ podmnožiny, což činí tuto metodu exponenciálním časem. Několik různých pastí může vytvořit algoritmus exponenciální čas, ale místo toho, abyste hledali široké kategorie, analyzujte algoritmy případ od případu.
-
Pokud algoritmus dokončí kroky $ n ^ 2 $, pak je polynomický. Pokud trvá kroky $ 2 ^ n $, je exponenciální. Rozdíl je v pozici $ n $. Pokud je něco $ O (n ^ m) $ za $ n > 1 $, $ m > 0 $, pak je to polynom v $ n $ pro pevné $ m $, ale exponenciální v $ m $ pro pevné $ n $.
Komentáře
- Opatrně. Funkce $ n ^ m $ isn ' t polynomial v $ n $, pokud $ m $ není konstanta. A pokud $ m $ je konstanta, ' nemá smysl říkat, že funkce je v této konstantě exponenciální.
- Ano, vy ' máte pravdu. ' to objasním.
Odpovědět
Když vezmete v úvahu problém a získáte výčet jeho celého vyhledávacího prostoru, získáte exponenciální časový algoritmus hrubé síly. Typicky byste uvažovali o problémech s podmnožinou (v SAT byste vybrali podmnožinu proměnné nastavené na hodnotu true), problémy s permutací (v TSP je každá prohlídka permutací měst) a problémy s oddíly (v barvení grafů se snažíte p umění vrcholy do barevných tříd). Nebo zvažte rovnoměrné třídění: existují $ n! $ Permutace celých čísel $ n $. Projděte každou permutaci a zkontrolujte, zda je tříděna. Hloupé (a pomalé), ale funguje to.
Komentáře
- Je třeba si uvědomit, že $ O (n!) $ Je ještě horší než $ O ( k ^ n) $. Pokud se ' stále snažíte dozvědět více o časové složitosti, může to být užitečná věc, kterou si sami prokážete.