NTIME

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de complexiteitstheorie is NTIME( f(n) ) een complexiteitsklasse die alle beslissingsproblemen bevat die in O(f(n)) opgelost kunnen worden door een niet-deterministische Turingmachine.

Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van NTIME. Zo kan NP gedefinieerd worden als

\cup_{k=1}^{\infty} \text{NTIME}(n^k)

en NEXPTIME als

\cup_{k=1}^{\infty} \text{NTIME}(2^{n^k}).

In verhouding tot DTIME geldt dat DTIME(f(n)) ⊆ 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 deterministische Turingmachine.

Externe links[bewerken]