NTIME
I kompleksitetsteori , NTIME betegner en familie af kompleksitet klasser karakteriseret ved deres tidskompleksitet på en ikke-deterministisk Turing-maskine .
Mere præcist er klassen af beslutningsproblemer, som for en størrelse input kan løses med en ikke-deterministisk Turing maskine.
IKKETjegME(f(ikke)){\ displaystyle {\ mathsf {NTIME}} (f (n))}ikke{\ displaystyle n}O(f(ikke)){\ displaystyle {\ mathcal {O}} (f (n))}
Definitioner
NP- klassen af beslutningsproblemer, der kan afgøres af en ikke-deterministisk Turing-maskine i polynomisk tid med hensyn til størrelsen af input kan defineres som:
IKKEP=⋃k∈IKKEIKKETjegME(ikkek){\ displaystyle {\ mathsf {NP}} = \ bigcup \ limit _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} (n ^ {k})}Ligeledes defineres NEXPTIME- klassen af beslutningsproblemer, der kan afgøres af en ikke-deterministisk Turing-maskine i eksponentiel tid som:
IKKEExPTjegME=⋃k∈IKKEIKKETjegME(2ikkek){\ displaystyle {\ mathsf {NEXPTIME}} = \ bigcup \ limit _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} \ left (2 ^ {n ^ {k}} \ right)}
Tidshierarki
Uformelt indikerer den ikke-deterministiske tidshierarki sætning, at det at have mere tid gør det muligt at beslutte flere problemer. Mere præcist, for alle funktioner og sådan, at og øges og konstrueres i tide , er følgende strenge inkludering verificeret:
f{\ displaystyle f}g{\ displaystyle g}f(ikke+1)=o(g(ikke)){\ displaystyle f (n + 1) = o (g (n))}g{\ displaystyle g}
IKKETjegME(f(ikke))⊊IKKETjegME(g(ikke)){\ displaystyle {\ mathsf {NTIME}} (f (n)) \ subsetneq {\ mathsf {NTIME}} (g (n))}
Links til andre klasser
De NTIME klasser er forbundet med den deterministiske tid kompleksitetsklasser dTime og til pladskompleksitet klasser DSpace og NSPACE ved de følgende inklusioner til ethvert constructible funktion i rummet:
f{\ displaystyle f}
DTjegME(f(ikke))⊆IKKETjegME(f(ikke))⊆DSPPÅVSE(f(ikke))⊆IKKESPPÅVSE(f(ikke))⊆DTjegME(2O(f(ikke))){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subseteq {\ mathsf {NTIME}} (f (n)) \ subseteq {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DTIME}} \ left (2 ^ {{\ mathcal {O}} (f (n))} \ right)}Bibliografi
-
(en) Sanjeev Arora og Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,20. april 2009, 579 s. ( ISBN 978-0-521-42426-4 , læs online ).
-
Sylvain Perifel, algoritmisk kompleksitet , Editions Ellipses ,22. april 2014, 432 s. ( ISBN 978-2-729-88692-9 , læs online ).