Кіріспе
Уақыт берілгенде, Тьюринг машинасы көбірек мәселелерді шеше алады. Есептеу күрделілігі теориясында, уақыт иерархиясы теоремалары – Тьюринг машиналарында уақытпен шектелген есептеулер туралы маңызды тұжырымдар. Формальды түрде, бұл теоремалар көбірек уақыт берілгенде, Тьюринг машинасы көбірек мәселелерді шеше алады дейді. Мысалы, n² уақытында, бірақ n уақытында емес, шешілетін мәселелер бар, мұндағы n – кіріс ұзындығы. Детерминистік көп таспалы Тьюринг машиналары үшін уақыт иерархиясы теоремасын алғаш рет Ричард Э. Стернс және Юрис Хартманис 1965 жылы дәлелдеді. Бір жылдан кейін Ф. С. Хенни мен Ричард Э. Стернс Универсалды Тьюринг машинасының тиімділігін жақсартқанда ол жақсартылды. Теоремаға сәйкес, әрбір детерминистік уақытпен шектелген күрделілік класы үшін, уақытпен шектелген күрделілік класы қатаң түрде үлкен болады, сондықтан күрделілік кластарының уақытпен шектелген иерархиясы толығымен құлап кетпейді. Нақтырақ айтқанда, детерминистік Тьюринг машиналары үшін уақыт иерархиясы теоремасы барлық уақыт құрастырылатын функциялар үшін f(n) келесідей:
,
мұндағы DTIME(f(n)) – уақыт O(f(n)) ішінде шешілетін шешім проблемаларының күрделілік класын білдіреді. Сол жақ класы кішкентай o белгісін қамтиды, бұл f(n) уақытынан асимптотикалық түрде аз уақытта шешілетін шешім проблемаларының жиынтығын білдіреді. Атап айтқанда, бұл егер және тек қана , онда бізде шексіз уақыт иерархиясы бар екенін көрсетеді. Детерминистік емес Тьюринг машиналары үшін уақыт иерархиясы теоремасын алғаш рет Стивен Кук 1972 жылы дәлелдеді. Ол 1978 жылы Жоел Сейферас, Майкл Фишер және Альберт Мейердің күрделі дәлелдемесі арқылы қазіргі түріне жетті. Соңында, 1983 жылы Станислав Жак бүгінгі күні оқытылатын қарапайым дәлелдемемен бірдей нәтижеге қол жеткізді. Детерминистік емес Тьюринг машиналары үшін уақыт иерархиясы теоремасы g(n) уақыт құрастырылатын функция болса және f(n+1) = o(g(n)), онда
.
Кеңістікке арналған аналогты теоремалар – кеңістік иерархиясы теоремалары. Уақытпен шектелген ықтималдық күрделілік кластары үшін осыған ұқсас теорема белгілі емес, егер класта бір бит кеңес болмаса.
In computational complexity theory, the time hierarchy theorems are important statements about time bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time, where n is the input length. The time hierarchy theorem for deterministic multi tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the Universal Turing machine. Consequent to the theorem, for every deterministic time bounded complexity class, there is a strictly larger time bounded complexity class, and so the time bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time constructible functions f(n),
,
where DTIME(f(n)) denotes the complexity class of decision problems solvable in time O(f(n)). The left hand class involves little o notation, referring to the set of decision problems solvable in asymptotically less than f(n) time. In particular, this shows that if and only if , so we have an infinite time hierarchy. The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time constructible function, and f(n+1) = o(g(n)), then
The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time bounded probabilistic complexity classes, unless the class also has one bit of advice.
Өмірбаян
Екі теорема да уақыт бойынша құрастырылатын функция түсінігін қолданады. Функция уақыт бойынша құрастырылатын болып есептеледі, егер детерминистік Тьюринг машинасы болса, онда машина n бірлік сандарымен басталып, дәл f(n) қадамнан кейін тоқтаса. Оң және нөлдік бүтін сан коэффициенттері бар барлық полиномдар, сондай-ақ 2^n сияқты экспоненциалдық функциялар уақыт бойынша құрастырылатын.
Дәлелдің жалпы көрінісі
Бізге белгілі бір уақыт класы TIME(g(n)) белгілі бір уақыт класы TIME(f(n))-ден қатаң үлкен екенін дәлелдеу қажет. Мұны диагональдау арқылы TIME(f(n))-де болмайтын машинаны құрастыру арқылы жасаймыз. Содан кейін, симулятор машинасын қолданып, бұл машинаның TIME(g(n))-де екенін көрсетеміз.
Айтылым
Уақыт иерархиясы теоремасы. Егер f(n) уақыт құрастырылатын функция болса, онда ең нашар жағдайда детерминистік уақытпен o(f(n)) шешілмейтін, бірақ ең нашар жағдайда детерминистік уақытпен O(f(n)log f(n)) шешілетін шешім проблемасы бар. Осылайша,
1-ескертпе. f(n) кем дегенде n болуы керек, себебі кіші функциялар ешқашан уақыт құрастырылмайды. Мысал. nlog2n уақытында шешілетін, бірақ n уақытында шешілмейтін проблемалар бар. Бұл n функциясы кіретіндіктен осылай шығады.