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ść).

Klasy złożoności w DTIME

Wiele ważnych klas złożoności jest zdefiniowanych za pomocą DTIME, zawierających wszystkie problemy, które można rozwiązać w określonym czasie deterministycznym.

DTIME spełnia twierdzenie o hierarchii czasu, co oznacza, że asymptotycznie większe ilości czasu zawsze tworzą ściśle większe zestawy problemów.

Dobrze znana klasa złożoności P obejmuje wszystkie problemy, które można rozwiązać w wielomianowej ilości DTIME. Można to formalnie zdefiniować jako:

${\displaystyle \mathrm {P} =\bigcup _{k\in \mathbb {N} }\mathrm {DTIME} (n^{k}).}$

Znacznie większa klasa wykorzystująca czas deterministyczny to EXPTIME, która zawiera wszystkie problemy, które można rozwiązać za pomocą maszyny deterministycznej w czasie wykładniczym. Formalnie mamy

${\displaystyle \mathrm {EXPTIME} =\bigcup _{k\in \mathbb {N} }\mathrm {DTIME} \left(2^{n^{k}}\right).}$

Większe klasy złożoności można zdefiniować podobnie. Z powodu twierdzenia o hierarchii czasu klasy te tworzą ścisłą hierarchię; wiemy, że ${\displaystyle \mathrm {P} \subsetneq \mathrm {EXPTIME} }$ i dalej.

Model maszyny

Dokładny model maszyny użyty do zdefiniowania DTIME może się różnić bez wpływu na moc DTIME. Wyniki w literaturze często wykorzystują wielotaśmowe maszyny Turinga, szczególnie przy omawianiu bardzo małych klas. W szczególności wielotaśmowa deterministyczna maszyna Turinga nigdy nie może zapewnić przyspieszenia większego niż kwadratowe w stosunku do maszyny jednotaśmowej^[1].

Uogólnienia

Używając modelu innego niż deterministyczna maszyna Turinga, istnieją różne uogólnienia i ograniczenia DTIME. Na przykład jeśli użyjemy niedeterministycznej maszyny Turinga, mamy klasę NTIME. Związek między mocą DTIME a mocami innych klas jest bardzo słabo poznany. Jednym z niewielu znanych wyników jest

${\displaystyle \mathrm {DTIME} (O(n))\neq \mathrm {NTIME} (O(n))}$

do maszyn z wieloma taśmami. Zostało to rozszerzone na

${\displaystyle \mathrm {DTIME} (O(n{\sqrt {\log ^{*}n}}))\neq \mathrm {NTIME} (O(n{\sqrt {\log ^{*}n}}))}$

przez Santhanama^[2].

Jeśli używamy naprzemiennej maszyny Turinga, mamy zasób ATIME.

Przypisy