DTIME

W teorii złożoności obliczeniowej DTIME jest klasą złożoności czasowej dla deterministycznej maszyny Turinga. Reprezentuje czas (lub liczbę kroków obliczeniowych), jaki „normalny” komputer poświęciłby na rozwiązanie określonego problemu obliczeniowego przy użyciu określonego algorytmu. Jest to jedna z najlepiej zbadanych klas złożoności, ponieważ ściśle odpowiada ważnemu zasobom w świecie rzeczywistym (ilości czasu potrzebnego komputerowi na rozwiązanie problemu).

Zasób DTIME służy do definiowania klas złożoności, zestawów wszystkich problemów decyzyjnych, które można rozwiązać za pomocą określonego czasu obliczeniowego. Jeśli problem rozmiaru wejściowego n można rozwiązać w ${\displaystyle O(f(n))}$ mamy klasę złożoności ${\displaystyle \mathrm {DTIME} (f(n))}$ (lub ${\displaystyle \mathrm {TIME} (f(n))}$). Nie ma ograniczeń co do ilości używanej pamięci, ale mogą istnieć ograniczenia dotyczące niektórych innych zasobów złożoności (takich jak przemienność).