WikiDer > NTIME

In dem Komplexitätstheorie ist NZEIT( f(n) ) ein Komplexitätsklasse diese alle Entscheidungsprobleme enthält das in Ö(f(n)) kann gelöst werden durch a nichtdeterministische Turingmaschine.

Viele bekannte Komplexitätsklassen können in Bezug auf NTIME definiert werden. so kann NP definiert werden als

${displaystyle cup _{k=1}^{infty }{ ext{NTIME}}(n^{k})}$

und NÄCHSTES ZEIT wenn

${displaystyle cup _{k=1}^{infty }{ ext{NTIME}}(2^{n^{k}})}$.

Relativ zu DTIME gilt DTIME(f(n)) ⊆ NTIME(f(n)) für jede Funktion f(n), da die benötigte Zeit auf einer nichtdeterministischen Turingmaschine, die keinen Nichtdeterminismus verwendet, gleich a . ist deterministische Turingmaschine.

Externer Link

• (und) NZEIT, Komplexität Zoo