DCZAS - DTIME

W teorii złożoności obliczeniowej , DTIME (lub CZAS ) jest obliczeniowa zasób od czasu obliczeń dla deterministycznej maszyny Turinga . Reprezentuje ilość czasu (lub liczbę kroków obliczeniowych), jaką „normalny” komputer fizyczny zająłby rozwiązanie określonego problemu obliczeniowego przy użyciu określonego algorytmu . Jest to jeden z najlepiej zbadanych zasobów złożoności, ponieważ tak ściśle odpowiada ważnemu zasobowi w świecie rzeczywistym (ilość czasu, jaką zajmuje komputerowi rozwiązanie problemu).

Zasób DTIME służy do definiowania klas złożoności , czyli zbiorów wszystkich problemów decyzyjnych, które można rozwiązać przy użyciu określonego czasu obliczeniowego. Jeśli problem wielkości wejściowej n można rozwiązać w , mamy klasę złożoności (lub ). Nie ma ograniczeń co do ilości używanej przestrzeni pamięci , ale mogą istnieć ograniczenia dotyczące niektórych innych zasobów złożoności (takich jak alternacja ). ${\ Displaystyle O (f (n))}$${\ Displaystyle {\ mathsf {DTIME}} (f (n))}$${\ Displaystyle {\ mathsf {CZAS}} (f (n))}$

Klasy złożoności w DTIME

Wiele ważnych klas złożoności jest zdefiniowanych w kategoriach DTIME , zawierających wszystkie problemy, które można rozwiązać w określonym czasie deterministycznym. Każda właściwa funkcja złożoności może być użyta do zdefiniowania klasy złożoności, ale tylko niektóre klasy są przydatne do badania. Ogólnie rzecz biorąc, chcemy, aby nasze klasy złożoności były odporne na zmiany w modelu obliczeniowym i były zamknięte w ramach kompozycji podprogramów.

DTIME spełnia twierdzenie o hierarchii czasu , co oznacza, że asymptotycznie większa ilość czasu zawsze tworzy ściśle większe zbiory problemów.

Dobrze znana klasa złożoności P obejmuje wszystkie problemy, które można rozwiązać za pomocą wielomianu DTIME . Formalnie można go zdefiniować jako:

${\ Displaystyle {\ mathsf {P}} = \ bigcup _ {k \ w \ mathbb {N}} {\ mathsf {DTIME}} (n ^ {k})}$

P jest najmniejszą odporną klasą, która obejmuje zagadnienia czasu liniowego (AMS 2004, Lecture 2.2, s. 20). P jest jedną z największych klas złożoności uważanych za „wykonalne obliczeniowo”. ${\ Displaystyle {\ mathsf {DTIME}} \ lewo (n \ prawo)}$

Dużo większą klasą używającą czasu deterministycznego jest EXPTIME , która zawiera wszystkie problemy, które można rozwiązać przy użyciu maszyny deterministycznej w czasie wykładniczym . Formalnie mamy

${\ Displaystyle {\ mathsf {EXPTIME}} = \ bigcup _ {k \ w \ mathbb {N}} {\ mathsf {DTIME}} \ lewo (2 ^ {n ^ {k}} \ po prawej).}$

Podobnie można zdefiniować większe klasy złożoności. Ze względu na twierdzenie o hierarchii czasu klasy te tworzą ścisłą hierarchię; wiemy, że i dalej. ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$

Model maszyny

Dokładny model maszyny używany do definiowania DTIME może się różnić bez wpływu na moc zasobu. Wyniki w literaturze często wykorzystują wielotaśmowe maszyny Turinga , szczególnie przy omawianiu bardzo małych zajęć czasowych. W szczególności wielotaśmowa deterministyczna maszyna Turinga nigdy nie może zapewnić przyspieszenia w czasie większym niż kwadratowe w porównaniu z maszyną jednotaśmową.

Stałe multiplikatywne w użytym czasie nie zmieniają potęgi klas DTIME; stałe przyspieszenie multiplikatywne można zawsze uzyskać zwiększając liczbę stanów w skończonej kontroli stanów. W oświadczeniu Papadimitriou dla języka L ,

Niech . Następnie dla dowolnego , , gdzie .${\ Displaystyle L \ w {\ mathsf {DTIME}} (f (n))}$${\ Displaystyle \ epsilon > 0}$${\ Displaystyle L \ w {\ mathsf {DTIME}} (f'(n))}$${\ Displaystyle f '(n) = \ epsilon f (n) + n + 2}$

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żywamy niedeterministycznej maszyny Turinga , mamy zasób NTIME . Związek między mocami ekspresyjnymi DTIME a innymi zasobami obliczeniowymi jest bardzo słabo poznany. Jednym z niewielu znanych wyników jest

${\ Displaystyle {\ mathsf {DTIME}} (O (n)) \ neq {\ mathsf {NTIME}} (O (n))}$

dla maszyn wielotaśmowych. Zostało to rozszerzone do

${\ Displaystyle {\ mathsf {DTIME}} (O (n {\ sqrt {\ log ^ {*} n}})) \ neq {\ mathsf {NTIME}} (O (n {\ sqrt {\ log ^ { *}n}}))}$

przez Santhanam.

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

Bibliografia

• Amerykańskie Towarzystwo Matematyczne (2004). Rudich, Steven i Avi Wigderson (red.). Teoria złożoności obliczeniowej . Amerykańskie Towarzystwo Matematyczne i Instytut Studiów Zaawansowanych . Numer ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. (1994). Złożoność obliczeniowa . Czytanie, Massachusetts: Addison-Wesley. Numer ISBN 0-201-53082-1.