Brontekst bekijken van NTIME

In de [[complexiteitstheorie]] is '''NTIME( f(n) )''' een [[complexiteitsklasse]] die alle [[Beslissingsprobleem|beslissingsproblemen]] bevat die in [[Complexiteitsgraad|O]](f(n)) opgelost kunnen worden door een [[Turingmachine|niet-deterministische turingmachine]].

Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van NTIME. 
Zo kan [[NP (complexiteitsklasse)|NP]] gedefinieerd worden als 
:<math>\cup_{k=1}^{\infty} \text{NTIME}(n^k)</math> 
en [[NEXPTIME]] als 
:<math>\cup_{k=1}^{\infty} \text{NTIME}(2^{n^k})</math>. 
In verhouding tot [[DTIME]] geldt dat DTIME(f(n)) &sube; NTIME(f(n)) voor elke functie f(n) aangezien de benodigde tijd op een niet-deterministische turingmachine die geen niet-determinisme gebruikt gelijk is aan een [[Turingmachine|deterministische turingmachine]].

== Externe link ==
*{{en}} [https://web.archive.org/web/20100727020050/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AN#ntime NTIME], [[Complexity Zoo]]

[[Categorie:Complexiteitsklasse]]