DTIME
Sign in to saveIn computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem).
Article · Polski
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 mamy klasę złożoności (lub ). 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ść).
Abstract from DBpedia / Wikipedia · CC BY-SA