Кеңістік иерархиясы теоремалары: Детерминистік және недетерминистік машиналар

Кіріспе

Детерминистік және детерминистік емес машиналар да көбірек орын берілген кезде көбірек мәселелерді шеше алады. Есептеу күрделілігі теориясында кеңістік иерархиясы теоремалары – бұл детерминистік және детерминистік емес машиналардың белгілі бір шарттарда (асимптотикалық) көбірек кеңістікте көбірек мәселелерді шеше алатынын көрсететін ажырату нәтижелері. Мысалы, детерминистік Тьюринг машинасы n log n кеңістікте n кеңістігіндегі шешімдік мәселелерді көбірек шеше алады. Уақытқа қатысты салыстырмалы теоремалар сәл әлсіз, олар уақыт иерархиясы теоремалары деп аталады. Иерархиялық теоремалардың негізі – уақыт пен кеңістік көлемі ұлғайған сайын, көбірек функцияларды есептеуге (немесе көбірек тілдерді шешуге) мүмкіндік туады деген түсінік. Иерархиялық теоремалар уақыт және кеңістік күрделілігі кластары иерархия құрайтынын көрсету үшін қолданылады, онда қатаң шектеулері бар кластарда, кеңірек шектеулері бар кластарға қарағанда аз тілдер болады. Осы жерде біз кеңістік иерархиясы теоремасын анықтап, дәлелдейміз. Кеңістік иерархиясы теоремалары кеңістікте құрастырылатын функциялар тұжырымына сүйенеді. Детерминистік және детерминистік емес кеңістік иерархиясы теоремалары барлық кеңістікте құрастырылатын f(n) функциялары үшін , мұнда SPACE – DSPACE немесе NSPACE дегенді білдіреді, ал o – кіші o белгісін білдіреді.

Ғарыш иерархиясының жетілдірілуі

Егер кеңістік алфавит мөлшеріне қарамастан қолданылатын жасушалардың саны ретінде өлшенсе, онда 1 = SPACE(f(n)) = SPACE(O(f(n))), өйткені үлкен әліпбиге ауысу арқылы кез келген сызықтық сығылуға қол жеткізуге болады. Дегенмен, кеңістікті биттермен өлшеу арқылы детерминистік кеңістік үшін әлдеқайда нақтырақ бөлінуге қол жеткізіледі. Көбейту тұрақтысына дейін анықталудың орнына, кеңістік енді қосу тұрақтысына дейін анықталады. Алайда, ішкі күйге мазмұнды сақтау арқылы сыртқы кеңістіктің кез келген тұрақты мөлшерін үнемдеуге болады, сондықтан бізде әлі де 1 = SPACE(f(n)) = SPACE(f(n) + O(1)). f кеңістік құрастырылатын деп есептейік. SPACE детерминистік. Тюринг машиналарын қоса алғанда, әртүрлі тізбекті есептеу модельдері үшін SPACE(f(n) ω(log(f(n) + n))) ⊂ SPACE(f(n)). Бұл тіпті SPACE(f(n) ω(log(f(n) + n))) басқа есептеу моделімен анықталған жағдайда да орындалады, өйткені әртүрлі модельдер бір-бірін O(log(f(n) + n)) кеңістіктік жүктемемен симуляциялай алады. Кейбір есептеу модельдері үшін, тіпті SPACE(f(n) ω(1)) ⊂ SPACE(f(n)) бар. Атап айтқанда, бұл Тюринг машиналары үшін, егер біз әліпбиді, кіріс таспасындағы бас санын, жұмыс таспасындағы бас санын (бір жұмыс таспасын пайдалана отырып) және жұмыс таспасының араланған бөлігіне делимитерлерді қоссақ (оларды кеңістікті ұлғайтпай тексеруге болады). SPACE(f(n)) жұмыс таспасының шексіз немесе жартылай шексіз болуына байланысты емес. f(n) егер таспаға арналған орынды пайдалануды көрсететін SPACE құрастырылатын тупл немесе жалпы орынды пайдалануды көрсететін (әр таспаның ұзындығын сақтау үшін үстеме шығындарды есептемегенде) SPACE(f(n) ω(log(f(n)))) құрастырылатын сан болса, бізде жұмыс таспаларының тұрақты саны болуы мүмкін. Дәлел кеңістіктегі иерархия теоремасының дәлеліне ұқсас, бірақ екі қиындық бар: әмбебап Тюринг машинасы кеңістік бойынша тиімді болуы керек, ал кері айналу кеңістік бойынша тиімді болуы керек. Универсалды Тюринг машиналарын O(log(space)) кеңістіктік жүктемемен және тиісті болжамдар бойынша тек O(1) кеңістіктік жүктемемен құрастыруға болады (бұл симуляцияланатын машинаға байланысты болуы мүмкін). Кері айналу үшін негізгі мәселе – симуляцияланған машина шексіз (кеңістік шектеулі) циклға кіріп, бас тартса, оны қалай анықтау керек. Тек қадамдарды санау кеңістік тұтынуын шамамен f(n)-ға арттырады. Потенциалды экспоненциалды уақытты ұлғайту есебінен, циклдарды кеңістік бойынша тиімді түрде келесідей анықтауға болады: Машинаны бәрін өшіру үшін өзгертіңіз және сәттілік кезінде белгілі бір конфигурацияға ауысыңыз. Бастапқы конфигурациядан бастап шектелген кеңістікте А-ға жетуге болатынын анықтау үшін тереңдікке бірінші іздеуді пайдаланыңыз. Іздеу А-дан басталады және А-ға әкелетін конфигурацияларды қайталайды. Детерминизмнің арқасында бұл орындалуы мүмкін және циклге кірмейді. Сондай-ақ, машина кеңістік шегінен асып кете ме (кеңістіктегі шеңберге қарама-қарсы) кеңістік шегінен асып кететін барлық конфигурацияларды қайталау арқылы және бастапқы конфигурация олардың кез келгеніне әкелсе, оны тексеру арқылы (қайта тереңдікке бірінші іздеуді қолдану арқылы) анықтауға болады.

If space is measured as the number of cells used regardless of alphabet size, then 1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(O(f(n))) because one can achieve any linear compression by switching to a larger alphabet. However, by measuring space in bits, a much sharper separation is achievable for deterministic space. Instead of being defined up to a multiplicative constant, space is now defined up to an additive constant. However, because any constant amount of external space can be saved by storing the contents into the internal state, we still have 1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(f(n)+O(1)). Assume that f is space constructible. SPACE is deterministic. For a wide variety of sequential computational models, including for Turing machines, SPACE(f(n) ω(log(f(n)+n))) ⊊ SPACE(f(n)). This holds even if SPACE(f(n) ω(log(f(n)+n))) is defined using a different computational model than \mathsf{SPACE}(f(n)) because the different models can simulate each other with O(\log(f(n)+n)) space overhead. For certain computational models, we even have SPACE(f(n) ω(1)) ⊊ SPACE(f(n)). In particular, this holds for Turing machines if we fix the alphabet, the number of heads on the input tape, the number of heads on the worktape (using a single worktape), and add delimiters for the visited portion of the worktape (that can be checked without increasing space usage). SPACE(f(n)) does not depend on whether the worktape is infinite or semi infinite. We can also have a fixed number of worktapes if f(n) is either a SPACE constructible tuple giving the per tape space usage, or a SPACE(f(n) ω(log(f(n))) constructible number giving the total space usage (not counting the overhead for storing the length of each tape). The proof is similar to the proof of the space hierarchy theorem, but with two complications: The universal Turing machine has to be space efficient, and the reversal has to be space efficient. One can generally construct universal Turing machines with O(\log(space)) space overhead, and under appropriate assumptions, just O(1) space overhead (which may depend on the machine being simulated). For the reversal, the key issue is how to detect if the simulated machine rejects by entering an infinite (space constrained) loop. Simply counting the number of steps taken would increase space consumption by about f(n). At the cost of a potentially exponential time increase, loops can be detected space efficiently as follows:

Modify the machine to erase everything and go to a specific configuration A on success. Use depth first search to determine whether A is reachable in the space bound from the starting configuration. The search starts at A and goes over configurations that lead to A. Because of determinism, this can be done in place and without going into a loop. It can also be determined whether the machine exceeds a space bound (as opposed to looping within the space bound) by iterating over all configurations about to exceed the space bound and checking (again using depth first search) whether the initial configuration leads to any of them.