NTIME

I kompleksitet teori , NTIME betegner en familie av kompleksitet klasser som er kjennetegnet ved sin tid kompleksitet på en ikke-determinis Turing maskin .

Mer presist, er klassen av beslutningsproblemer som for en størrelse input kan løses av en ikke-deterministisk Turing maskin. IKKETJegME(f(ikke)){\ displaystyle {\ mathsf {NTIME}} (f (n))}ikke{\ displaystyle n}O(f(ikke)){\ displaystyle {\ mathcal {O}} (f (n))}

Definisjoner

NP- klassen av beslutningsproblemer som kan bestemmes av en ikke-deterministisk Turing-maskin i polynomisk tid med hensyn til størrelsen på inngangen, kan defineres som:

IKKEP=⋃k∈IKKEIKKETJegME(ikkek){\ displaystyle {\ mathsf {NP}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} (n ^ {k})}

På samme måte er NEXPTIME- klassen av beslutningsproblemer som kan avgjøres av en ikke-deterministisk Turing-maskin i eksponensiell tid definert som:

IKKEEXPTJegME=⋃k∈IKKEIKKETJegME(2ikkek){\ displaystyle {\ mathsf {NEXPTIME}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} \ left (2 ^ {n ^ {k}} \ right)}

Tidshierarki

Uformelt indikerer den ikke-deterministiske tidshierarki-teorem at det å ha mer tid gjør at flere problemer kan avgjøres. Mer presist, for alle funksjoner og slik at og er økende og constructible i tid , er følgende strenge inklusjons bekreftet: 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))}

Koblinger til andre klasser

NTIME-klassene er knyttet til de deterministiske tidskompleksitetsklassene DTIME og til romkompleksitetsklassene DSPACE og NSPACE ved følgende inneslutninger, for enhver konstruerbar funksjon i rommet: 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 , les online ). 
• Sylvain Perifel, algoritmisk kompleksitet , Editions Ellipses ,22. april 2014, 432  s. ( ISBN  978-2-729-88692-9 , les online ).