NTIME
A komplexitás elmélet , NTIME jelöl család bonyolultsági osztályok által jellemzett időbonyolultsága egy nem-determinisztikus Turing-gép .
Pontosabban, az osztály a döntési problémák , amelyek a méret bemenet , lehet időben megoldható egy nem determinisztikus Turing-gép.
NEMTénME(f(nem)){\ displaystyle {\ mathsf {NTIME}} (f (n))}nem{\ displaystyle n}O(f(nem)){\ displaystyle {\ mathcal {O}} (f (n))}
Definíciók
A nem determinisztikus Turing-gép által polinomiális időben eldönthető döntési problémák NP osztálya a bemenet méretéhez viszonyítva a következőképpen határozható meg:
NEMP=⋃k∈NEMNEMTénME(nemk){\ displaystyle {\ mathsf {NP}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} (n ^ {k})}Hasonlóképpen, a NEXPTIME döntési problémák osztálya , amelyet egy nem determinisztikus Turing-gép exponenciális időben határoz meg, a következőképpen definiálható:
NEMExPTénME=⋃k∈NEMNEMTénME(2nemk){\ displaystyle {\ mathsf {NEXPTIME}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} \ left (2 ^ {n ^ {k}} \ right)}
Idő hierarchia
Informálisan a nemdeterminisztikus időhierarchia tétel azt jelzi, hogy több idő birtoklása több probléma eldöntését teszi lehetővé. Pontosabban, az összes funkcióhoz és így , és egyre növekszik, és beépíthető időben , a következő szigorú felvételi ellenőrzik:
f{\ displaystyle f}g{\ displaystyle g}f(nem+1)=o(g(nem)){\ displaystyle f (n + 1) = o (g (n))}g{\ displaystyle g}
NEMTénME(f(nem))⊊NEMTénME(g(nem)){\ displaystyle {\ mathsf {NTIME}} (f (n)) \ subsetneq {\ mathsf {NTIME}} (g (n))}
Kapcsolatok más osztályokkal
A NTIME osztályok kapcsolódnak a determinisztikus id bonyolultsági osztályok DTIME és a tér összetettsége osztályok DSPACE és NSPACE az alábbi felvételen, minden beépíthető funkció térben:
f{\ displaystyle f}
DTénME(f(nem))⊆NEMTénME(f(nem))⊆DSPNÁL NÉLVSE(f(nem))⊆NEMSPNÁL NÉLVSE(f(nem))⊆DTénME(2O(f(nem))){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subseteq {\ mathsf {NTIME}} (f (n)) \ subseteq {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DTIME}} \ bal (2 ^ {{\ mathcal {O}} (f (n))} \ jobb)}Bibliográfia
-
en) Sanjeev Arora és Boaz Barak , Számítási bonyolultság: modern megközelítés , Cambridge University Press ,2009. április 20, 579 p. ( ISBN 978-0-521-42426-4 , online olvasás ).
-
Sylvain Perifel, algoritmikus összetettség , Éditions Ellipses ,2014. április 22, 432 p. ( ISBN 978-2-729-88692-9 , online olvasás ).