DTIME

У теорији алгоритамске сложености, DTIME (или само TIME) је ресурс за одређивање времена за извршавање алгоритма у рачунару. Представља количину времена (или број рачунарских инструкција) потребних да обичан рачунар реши неки проблем користећи одговарајући алгоритам. ДТИМЕ је једна од највише изучаваних основа сложености, јер је уско повезана са реалним временом (временом које је потребно рачунару да реши проблем).

Ресурс ДТИМЕ се користи да би се одредиле класе сложености која представља скуп свих проблема који могу бити решени за одређени временски период. Ако је проблем улазне величине n захтева f(n) рачунарског времена да се реши, он припада класи DTIME(f(n)). Не постоји ограничење за меморијски простор неопходан да би се алгоритам извршио, али постоји за неке друге основе сложености.

Класе комплексности у DTIME

Многе важне класе сложености дефинисане у терминима ресурса DTIME, садрже све проблеме који могу бити решени у одређеној количини времена. Било која одговарајућа функција може бити искоришћена за одређивање класе сложености, али само неке класе је вредно изучавати. Уопштено, класе сложености одређују време решавања неког проблема независно од величине улаза.

DTIME основа уводи временску хијерархију проблема, што значи да се праве већи скупови проблема јер се асимптотски троши више времена.

Добро позната класа сложености P обухвата све проблеме који могу бити решени у полиномијалном времену. Може бити дефинисано као:

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

P је најмања класа која садржи проблеме линеарне сложености ${\mbox{DTIME}}\left(n\right)$ (AMS 2004, Lecture 2.2, pg. 20). P је највећа класа сложености која обухвата рачунарски изводљиве алгоритме.

Много већа класа која користи време решавање неког проблема је EXPTIME, која садржи све проблеме који се могу решити у експоненцијалном времену. Формално записано као:

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

Веће класе сложености се могу слично одредити. На основу временске хијерархије, ове класе формирају сопствену хијерархију, познато је да ${\mbox{P}}\subsetneq {\mbox{EXPTIME}}$.

Модел машине

Модел машине који одређује сложеност може бити произвољан без утицаја на моћ ресурса. У литератури се обично користе резултати модела Тјурингове машине са више трака, када се разматрају веома мале класе сложености. Детерминистичка Тјурингова машина са више трака не може никад да прикаже више од квадратне сложености за разлику од модела Тјурингове машине са једном траком (Papadimitriou 1994, Thrm. 2.1).

Мултипликативне константе у изразу не мењају класу сложености; мултипликативна константа убрзања се увек може постићи повећањем броја стања у коначној контроли стања. У тврђењу Пападимитрија (1994, Поглавље 2.2), за произвољан језик важи:

Нека је L $\in$ DTIME(f(n)). Тада, за било које $\epsilon$ > 0, L $\in$ DTIME(f'(n)), где је f'(n) = $\epsilon$ f(n) + n + 2.

Ограничења

Уколико се користи неки други модел од детерминистичког модела Тјурингове машине, постоје ограничења и изузеци са овим ресурсом. На пример, уколико се користи недетерминистичка Тјурингова машина, користи се NTIME ресурс. Веза између резултата различитих ресурса није лако схваћена. Један од резултата је

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

за модел машине са више трака. Уколико се користи наизменична Тјурингова машина, користи се ATIME ресурс.

Литература

• American Mathematical Society (2004). Steven Rudich and Avi Wigderson (ed.), ур. Computational Complexity Theory. American Mathematical Society and Institute for Advanced Study. 0-8218-2872-X.  CS1 одржавање: Текст вишка: списак уредника (веза)
• Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-53082-7.