Věta o časové hierarchii - Time hierarchy theorem

v teorie výpočetní složitosti, věty o časové hierarchii jsou důležitá tvrzení o časově omezeném výpočtu Turingovy stroje. Neformálně tyto věty říkají, že za více času může Turingův stroj vyřešit více problémů. Existují například problémy, které lze vyřešit n² čas, ale ne n čas.

Věta o časové hierarchii pro deterministické vícepásové Turingovy stroje bylo poprvé prokázáno Richard E. Stearns a Juris Hartmanis v roce 1965.^[1] To bylo vylepšeno o rok později, když F. C. Hennie a Richard E. Stearns zlepšili účinnost systému Univerzální Turingův stroj.^[2] Důsledek věty, pro každou deterministickou časově ohraničenou třída složitosti existuje striktně větší časově omezená třída složitosti, takže časově omezená hierarchie tříd složitosti se úplně nesbalí. Přesněji řečeno, věta o časové hierarchii pro deterministické Turingovy stroje říká, že pro všechny časově konstruovatelné funkce F(n),

{ displaystyle { mathsf {DTIME}} left (o left ({ frac {f (n)} { log f (n)}} right) right) subsetneq { mathsf {DTIME}} (f (n))}

.

Věta o časové hierarchii pro nedeterministické Turingovy stroje bylo původně prokázáno Stephen Cook v roce 1972.^[3] Do současné podoby byl vylepšen komplexním důkazem Joela Seiferase, Michael Fischer, a Albert Meyer v roce 1978.^[4] Konečně v roce 1983 dosáhl Stanislav Žák stejného výsledku s jednoduchým důkazem, který se dnes vyučuje.^[5] Věta o časové hierarchii pro nedeterministické Turingovy stroje uvádí, že pokud G(n) je časově konstruovatelná funkce a F(n+1) = Ó (G(n)), pak

{ displaystyle { mathsf {NTIME}} (f (n)) subsetneq { mathsf {NTIME}} (g (n))}

.

Analogické věty pro prostor jsou věty o vesmírné hierarchii. Podobná věta není známa pro časově omezené třídy pravděpodobnostní složitosti, pokud třída také nemá jeden bit Rada.^[6]

Pozadí

Obě věty používají pojem a časově konstruovatelná funkce. A funkce ${ displaystyle f: mathbb {N} rightarrow mathbb {N}}$ je časově konstruovatelný, pokud existuje deterministický Turingův stroj tak, že pro každého ${ displaystyle n in mathbb {N}}$ , pokud je stroj spuštěn se zadáním n ty, to se zastaví přesně F(n) kroky. Všechno polynomy s nezápornými celočíselnými koeficienty jsou časově konstruovatelné, stejně jako exponenciální funkce jako 2ⁿ.

Přehled důkazů

Musíme dokázat, že nějaká časová třída ČAS(G(n)) je přísně větší než nějaká časová třída ČAS(F(n)). Děláme to konstrukcí stroje, který nemůže být v ČAS(F(n)), tím diagonalizace. Poté ukážeme, že je stroj uvnitř ČAS(G(n)), používat simulátor.

Věta o deterministické časové hierarchii

Prohlášení

Věta o časové hierarchii. Li F(n) je časově konstruovatelná funkce, pak existuje a rozhodovací problém které nelze vyřešit v nejhorším případě deterministického času F(n), ale lze jej vyřešit v nejhorším deterministickém čase F(n)². Jinými slovy,
${ displaystyle { mathsf {DTIME}} (f (n)) subsetneq { mathsf {DTIME}} left (f (n) ^ {2} right).}$

Poznámka 1. F(n) je minimálně n, protože menší funkce nejsou nikdy časově konstruovatelné.

Poznámka 2. Ještě obecněji lze prokázat, že pokud F(n) je tedy časově proveditelný

{ displaystyle { mathsf {DTIME}} left (o left ({ frac {f (n)} { log f (n)}} right) right) subsetneq { mathsf {DTIME}} left (f (n) right).}

Například existují problémy řešitelné v čase n² ale ne čas n, od té doby n je v

{ displaystyle o left ({ frac {n ^ {2}} { log {n ^ {2}}}} right).}

Důkaz

Zde uvádíme důkaz DTIME(F(n)) je přísná podmnožina DTIME(F(2n + 1)³), protože je jednodušší. Ve spodní části této části najdete informace o tom, jak rozšířit důkaz na F(n)².

Abychom to dokázali, nejprve definujeme jazyk následujícím způsobem:

{ displaystyle H_ {f} = left {([M], x) | M { text {přijímá}} x { text {in}} f (| x |) { text {kroky}} doprava }.}

Tady, M je deterministický Turingův stroj a X je jeho vstup (počáteční obsah pásky). [M] označuje vstup, který kóduje Turingův stroj M. Nechat m být velikost n-tice ([M], X).

Víme, že můžeme rozhodnout o členství v H_F prostřednictvím deterministického Turingova stroje, který nejprve vypočítá F(|X|), poté vypíše řádek 0 s této délky a poté použije tento řádek 0 s jako „hodiny“ nebo „čítač“ k simulaci M nanejvýš tolik kroků. V každém kroku musí simulační stroj projít definicí M rozhodnout, jaká bude další akce. Lze s jistotou říci, že to trvá nanejvýš F(m)³ operace, tak

{ displaystyle H_ {f} in { mathsf {TIME}} left (f (m) ^ {3} right).}

Zbytek důkazu to ukáže

{ displaystyle H_ {f} notin { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right)}

takže když dosadíme 2n + 1 pro m, získáme požadovaný výsledek. Předpokládejme to H_F je v této časové třídě složitosti a pokusíme se dosáhnout rozporu.

Li H_F je v této časové třídě složitosti, to znamená, že můžeme postavit nějaký stroj K. který, vzhledem k určitému popisu stroje [M] a vstup X, rozhodne, zda n-tice ([M], X) je v H_F v rámci

{ displaystyle { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right).}

Proto to můžeme použít K. postavit další stroj, N, který přebírá popis stroje [M] a běží K. na n-tici ([M], [M]), a poté přijímá pouze pokud K. odmítá a odmítá, pokud K. přijímá. Pokud teď n je délka vstupu do N, pak m (délka vstupu do K.) je dvakrát n plus nějaký symbol oddělovače, takže m = 2n + 1. Ndoba provozu je tedy

{ displaystyle { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right) = { mathsf {TIME}} left (f left ( left lfloor { frac {2n + 1} {2}} right rfloor right) right) = { mathsf {TIME}} left (f (n) right) .}

Teď, když krmíme [N] jako vstup do N sám (což dělá n délka [N]) a zeptejte se, zda N přijímá svůj vlastní popis jako vstup, dostaneme:

Li N přijímá [N] (o kterém víme, že to funguje nanejvýš F(n) operace), to znamená, že K. odmítá ([N], [N]), tak ([N], [N]) není v H_F, a tudíž N nepřijímá [N] v F(n) kroky. Rozpor!
Li N odmítá [N] (o kterém víme, že to dělá maximálně.) F(n) operace), to znamená, že K. přijímá ([N], [N]), tak ([N], [N]) je v H_F, a tudíž N dělá akceptovat [N] v F(n) kroky. Rozpor!

Dospěli jsme tedy k závěru, že stroj K. neexistuje, a tak

{ displaystyle H_ {f} notin { mathsf {TIME}} left (f left ( left lfloor { frac {m} {2}} right rfloor right) right).}

Rozšíření

Čtenář si možná uvědomil, že důkaz je jednodušší, protože jsme zvolili jednoduchou simulaci Turingova stroje, u které si můžeme být jisti, že

{ displaystyle H_ {f} in { mathsf {TIME}} (f (m) ^ {3}).}

Ukázalo se to^[7] že existuje efektivnější model simulace, který to stanoví

{ displaystyle H_ {f} in { mathsf {TIME}} (f (m) log f (m))}

ale protože tento model simulace je spíše zapojen, není zde zahrnut.

Věta o nedeterministické časové hierarchii

Li G(n) je časově konstruovatelná funkce a F(n+1) = Ó (G(n)), pak existuje rozhodovací problém, který nelze vyřešit v nedeterministickém čase F(n), ale lze jej vyřešit v nedeterministickém čase G(n). Jinými slovy třída složitosti NTIME(F(n)) je přísná podmnožina NTIME(G(n)).

Důsledky

Věty o časové hierarchii zaručují, že deterministické a nedeterministické verze exponenciální hierarchie jsou skutečné hierarchie: jinými slovy P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... a NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....

Například, ${ displaystyle { mathsf {P}} subsetneq { mathsf {EXPTIME}}}$ od té doby ${ displaystyle { mathsf {P}} subseteq { mathsf {DTIME}} (2 ^ {n}) subsetneq { mathsf {DTIME}} (2 ^ {2n}) subseteq { mathsf {EXPTIME} }}$ . Vskutku, ${ displaystyle { mathsf {DTIME}} left (2 ^ {n} right) subseteq { mathsf {DTIME}} left (o left ({ frac {2 ^ {2n}} {2n}) } right) right) subsetneq { mathsf {DTIME}} (2 ^ {2n})}$ z věty o časové hierarchii.

Věta také zaručuje, že v ní jsou problémy P vyžadovat řešení libovolně velkých exponentů; jinými slovy, P neskolí na DTIME(n^k) pro všechny pevné k. Například existují problémy řešitelné v n⁵⁰⁰⁰ čas, ale ne n⁴⁹⁹⁹ čas. To je jeden argument proti Cobhamova teze konvence P je praktická třída algoritmů. Pokud by k takovému kolapsu došlo, mohli bychom to odvodit P ≠ PSPACE, protože se jedná o dobře známou větu DTIME(F(n)) je přísně obsažen v DSPACE(F(n)).

Věty o časové hierarchii však neposkytují žádné prostředky k propojení deterministické a nedeterministické složitosti nebo složitosti času a prostoru, takže nevrhají žádné světlo na velké nevyřešené otázky teorie výpočetní složitosti: zda P a NP, NP a PSPACE, PSPACE a EXPTIMEnebo EXPTIME a NEXPTIME jsou si rovni nebo ne.

Viz také

Věta o vesmírné hierarchii

Reference

^ Hartmanis, J.; Stearns, R. E. (1. května 1965). „O výpočetní složitosti algoritmů“. Transakce Americké matematické společnosti. Americká matematická společnost. 117: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. PAN 0170805.
^ Hennie, F. C .; Stearns, R. E. (Říjen 1966). „Simulace dvou pásků vícevrstvých Turingových strojů“. J. ACM. New York, NY, USA: ACM. 13 (4): 533–546. doi:10.1145/321356.321362. ISSN 0004-5411.
^ Cook, Stephen A. (1972). "Hierarchie pro nedeterministickou časovou složitost". Sborník příspěvků ze čtvrtého ročníku sympozia ACM o teorii práce s počítačem. STOC '72. Denver, Colorado, USA: ACM. 187–192. doi:10.1145/800152.804913.
^ Seiferas, Joel I .; Fischer, Michael J.; Meyer, Albert R. (Leden 1978). "Oddělení nedeterministických tříd časové složitosti". J. ACM. New York, NY, USA: ACM. 25 (1): 146–167. doi:10.1145/322047.322061. ISSN 0004-5411.
^ Žák, Stanislav (říjen 1983). "Časová hierarchie Turingova stroje". Teoretická informatika. Elsevier Science B.V. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4.
^ Fortnow, L .; Santhanam, R. (2004). "Věty o hierarchii pro pravděpodobnostní polynomiální čas". 45. výroční sympozium IEEE o základech informatiky. str. 316. doi:10.1109 / FOCS.2004.33. ISBN 0-7695-2228-9.
^ Luca Trevisan, Poznámky k větám o hierarchii, VIDÍŠ. Berkeley

Michael Sipser (1997). Úvod do teorie výpočtu. PWS Publishing. ISBN 0-534-94728-X. Stránky 310–313 v části 9.1: Věty o hierarchii.
Christos Papadimitriou (1993). Výpočetní složitost (1. vyd.). Addison Wesley. ISBN 0-201-53082-1. Část 7.2: Věta o hierarchii, s. 143–146.

[1] Hartmanis, J.; Stearns, R. E. (1. května 1965). „O výpočetní složitosti algoritmů“. Transakce Americké matematické společnosti. Americká matematická společnost. 117: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. PAN 0170805.

[2] Hennie, F. C .; Stearns, R. E. (Říjen 1966). „Simulace dvou pásků vícevrstvých Turingových strojů“. J. ACM. New York, NY, USA: ACM. 13 (4): 533–546. doi:10.1145/321356.321362. ISSN 0004-5411.

[3] Cook, Stephen A. (1972). "Hierarchie pro nedeterministickou časovou složitost". Sborník příspěvků ze čtvrtého ročníku sympozia ACM o teorii práce s počítačem. STOC '72. Denver, Colorado, USA: ACM. 187–192. doi:10.1145/800152.804913.

[4] Seiferas, Joel I .; Fischer, Michael J.; Meyer, Albert R. (Leden 1978). "Oddělení nedeterministických tříd časové složitosti". J. ACM. New York, NY, USA: ACM. 25 (1): 146–167. doi:10.1145/322047.322061. ISSN 0004-5411.

[5] Žák, Stanislav (říjen 1983). "Časová hierarchie Turingova stroje". Teoretická informatika. Elsevier Science B.V. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4.

[6] Fortnow, L .; Santhanam, R. (2004). "Věty o hierarchii pro pravděpodobnostní polynomiální čas". 45. výroční sympozium IEEE o základech informatiky. str. 316. doi:10.1109 / FOCS.2004.33. ISBN 0-7695-2228-9.

[7] Luca Trevisan, Poznámky k větám o hierarchii, VIDÍŠ. Berkeley

[1]

[2]

[3]

[4]

[5]

[6]

[7]