Изворни код странице DTIME

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

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

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

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

Добро позната класа сложености '''[https://en.wikipedia.org/wiki/P_%28complexity%29 P]''' обухвата све проблеме који могу бити решени у полиномијалном времену. Може бити дефинисано као: 

:<math>\mbox{P} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(n^k)</math>

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

Много већа класа која користи време решавање неког проблема је [[EXPTIME]], која садржи све проблеме који се могу решити у [[Експоненцијално време|експоненцијалном времену]]. Формално записано као:
:<math> \mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{DTIME} \left( 2^{ n^k } \right) . </math>

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

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

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

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

== Ограничења ==
Уколико се користи неки други модел од детерминистичког модела Тјурингове машине, постоје ограничења и изузеци са овим ресурсом.
На пример, уколико се користи [https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine недетерминистичка Тјурингова машина], користи се [https://en.wikipedia.org/wiki/NTIME NTIME] ресурс. Веза између резултата различитих ресурса
није лако схваћена. Један од резултата<ref>Paul Wolfgang, Nick Pippenger, Endre Szemerédi, William Trotter. On determinism versus non-determinism and related problems. {{cite book|title= 24th Annual Symposium on Foundations of Computer Science (SFCS 1983)|chapter= On determinism versus non-determinism and related problems|date= 1983|volume=|pages=429–438|doi=10.1109/SFCS.1983.39|last1= Paul|first1= Wolfgang J.|last2= Pippenger|first2= Nicholas|last3= Szemeredi|first3= Endre|last4= Trotter|first4= William T.|isbn= 0-8186-0508-1}}</ref> је 
:<math>\mathsf{DTIME}(O(n)) \neq \mathsf{NTIME}(O(n))</math>
за модел машине са више трака. Уколико се користи [https://en.wikipedia.org/wiki/Alternating_Turing_machine наизменична Тјурингова машина], користи се ATIME ресурс.	

== Референце ==
{{reflist}}

== Литература ==
* {{cite book
 | author = [https://en.wikipedia.org/wiki/American_Mathematical_Society American Mathematical Society]
 | editor = [https://en.wikipedia.org/wiki/Steven_Rudich Steven Rudich] and [https://en.wikipedia.org/wiki/Avi_Wigderson Avi Wigderson] (ed.)
 | title = Computational Complexity Theory
 | year=2004
 | publisher = [https://en.wikipedia.org/wiki/American_Mathematical_Society American Mathematical Society] and [https://en.wikipedia.org/wiki/Institute_for_Advanced_Study Institute for Advanced Study]
 | id= 0-8218-2872-X
}}
* {{cite book
 |last=Papadimitriou
 | first = Christos H.
 | authorlink = Christos Papadimitriou
 | year=1994
 | title = Computational Complexity
 |url=https://archive.org/details/computationalcom0000papa
 | publisher = Addison-Wesley
 | location = Reading, Massachusetts 
 | isbn=978-0-201-53082-7
}}

{{нормативна контрола}}

{{СОРТИРАЊЕ:Dtime}}

[[Категорија:Класе комплексности]]