WikiDer > DTIME

In dem Komplexitätstheorie ist DTIME(f(n)), auch bekannt als ZEIT(f(n)), ein Komplexitätsklasse diese alle Entscheidungsprobleme enthält die in Ö(f(nein)) Zeit kann durch a . gelöst werden deterministische Turingmaschine.

Viele bekannte Komplexitätsklassen lassen sich durch DTIME. so kann p definiert werden als ${displaystyle cup _{k=1}^{infty }{ ext{DTIME}}(n^{k})}$ und EXPTIME wenn ${displaystyle cup _{k=1}^{infty }{ ext{DTIME}}(2^{n^{k}})}$. Relativ zu NZEIT zählt das DTIME(f(n)) NZEIT(f(n)) für jede Funktion f(n) seit der benötigten Zeit auf a nichtdeterministische Turingmaschine die keinen Nichtdeterminismus verwendet, entspricht einer deterministischen Turingmaschine.

Externer Link

• (und) DTIME, Komplexität Zoo