PSPACE толық проблемалары: есептеу күрделілігі, полиномдық кеңістікте шешілетін ең қиын мәселелер. Регулярлы өрнектер, грамматикалар, ойындарды қамтиды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеу күрделілігі теориясында, шешім есебі PSPACE-толық деп аталады, егер оны кіріс ұзындығына (полиномиялық кеңістік) пропорционал жад көлемін пайдаланып шешуге болады, және егер кез келген басқа есеп, полиномиялық кеңістікте шешілетін болса, оған полиномиялық уақытта түрлендіріле алады. PSPACE-толық есептер PSPACE класындағы ең қиын есептер саналады, себебі мұндай есептің біреуін шешу арқылы PSPACE класындағы кез келген басқа есепті де оңай шешуге болады. PSPACE-толық екені белгілі есептерге: тұрақты өрнектер мен контекстке тәуелді грамматикалардың қасиеттерін анықтау, сандық Буль формулаларының дұрыстығын анықтау, комбинаторлық оптимизация есептерінің шешімдері арасындағы қадамдық өзгерістер, сондай-ақ көптеген жұмбақтар мен ойындар жатады.
In computational complexity theory, a decision problem is PSPACE complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. Problems known to be PSPACE complete include determining properties of regular expressions and context sensitive grammars, determining the truth of quantified Boolean formulas, step by step changes between solutions of combinatorial optimization problems, and many puzzles and games.
Теория
Мәселе PSPACE толық деп есептеледі, егер оны полиномдық көлемде жадты пайдаланып шешуге болады (яғни ол PSPACE класына жатады) және PSPACE класындағы кез келген мәселені полиномдық уақытта берілген мәселенің эквивалентті мысалына түрлендіруге болады. PSPACE толық мәселелерінің P (полиномдық уақыт) және NP (детерминистік емес полиномдық уақыт) сияқты белгілі күрделілік кластарынан тыс екені күдік тудырады, бірақ бұл әлі дәлелденбеді. Олар NC класынан тыс екені белгілі, себебі NC класындағы мәселелер кірістің логарифміне қатысты полиномдық көлемдегі жадты пайдаланып шешіледі, ал мұндай шағын көлемдегі жадты пайдаланатын мәселелер класы кеңістік иерархиясы теоремасы бойынша PSPACE класына толығымен кіріктірілген. PSPACE толықтығын анықтауда көбінесе полиномдық уақытты көп-бірге азайтулар қарастырылады, яғни бір типтегі мәселенің бір мысалын екінші типтегі мәселенің эквивалентті бір мысалына түрлендіретін түрлендірулер. Алайда, толықтықты Тьюринг азайтуларын қолдана отырып анықтауға да болады, онда бір мәселені екінші мәселенің процедурасын полиномдық санымен шақыру арқылы шешуге болады. Бұл екі түрдегі азайтулар PSPACE толық мәселелерінің әртүрлі кластарын құрайтыны белгісіз. Сондай-ақ, әрқашан түрлендірілген кірістің ұзындығын ұлғайтатын көп-бірге азайтулар сияқты басқа азайту түрлері де қарастырылған. PSPACE толық жиындар үшін Берман-Хартманис болжамының нұсқасы бойынша, мұндай жиындардың барлығы бір-біріне ұқсас, яғни оларды полиномдық уақыттық биекциялар арқылы бір-біріне түрлендіруге болады.
A problem is defined to be PSPACE complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be transformed in polynomial time into an equivalent instance of the given problem. The PSPACE complete problems are widely suspected to be outside the more famous complexity classes P (polynomial time) and NP (non deterministic polynomial time), but that is not known. It is known that they lie outside of the class NC, a class of problems with highly efficient parallel algorithms, because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem. The transformations that are usually considered in defining PSPACE completeness are polynomial time many one reductions, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using Turing reductions, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE complete problems. Other types of reductions, such as many one reductions that always increase the length of the transformed input, have also been considered. A version of the Berman–Hartmanis conjecture for PSPACE complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial time bijections.
Ресми тілдер
Кез келген үлгі өрнегі берілгенде, оның алфавитіндегі барлық тізбектерді тудыратынын анықтау PSPACE толық проблемасы болып табылады. PSPACE толық проблемасының алғашқы белгілі мысалы – детерминистік контекстке сезімтал грамматиканың сөздік проблемасы. Контекстке сезімтал грамматиканың сөздік проблемасында, сөйлемнің ұзындығын ұлғайта бірақ қысқарта алмайтын грамматикалық түрлендірулер жиынтығы беріледі, және берілген сөйлемнің осы түрлендірулер арқылы туындатылуы мүмкін бе екенін анықтау қажет. "Детерминизм" шарттары (әр түрлендірудің қолданылғанын анық көрсетеді) бұл процестің полиномдық кеңістікте шешілуін қамтамасыз етеді, сондай-ақ сызықтық кеңістікте есептелетін кез келген (мүмкін детерминистік емес) бағдарламаны детерминизмді сақтай отырып, контекстке сезімтал грамматиканы талдауға түрлендіруге болатынын көрсетті. 1970 жылы Савич теоремасы PSPACE-нің нондетерминизмге қатысты жабық екенін көрсетті, яғни тіпті детерминистік емес контекстке сезімтал грамматика да PSPACE-де орналасады.
Given a regular expression , determining whether it generates every string over its alphabet is PSPACE complete. The first known PSPACE complete problem was the word problem for deterministic context sensitive grammars. In the word problem for context sensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations. The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and showed that every (possibly non deterministic) program computable in linear space could be converted into the parsing of a context sensitive grammar, in a way which preserves determinism. In 1970, Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even non deterministic context sensitive grammars are in PSPACE.
Логика
PSPACE-тің көптеген басқа да толық нәтижелерінде қолданылатын стандартты PSPACE толық мәселесі – Бульдық формуланың сандықталған түрі, Бульдық қанағаттандырылатындық мәселесінің жалпыламасы. Сандықталған Бульдық формула мәселесі кіріс ретінде Бульдық өрнекті қабылдайды, оның барлық айнымалылары универсалды немесе экзистенциалды түрде сандықталған, мысалы:
A standard PSPACE complete problem, used in many other PSPACE completeness results, is the quantified Boolean formula problem, a generalization of the Boolean satisfiability problem. The quantified Boolean formula problem takes as input a Boolean expression, with all of its variables quantified either universally or existentially, for example:
Мәселенің нәтижесі – сандықталған өрнектің мәні. Бұл мәнді табу PSPACE толық.
The output of the problem is the value of the quantified expression. Finding this value is PSPACE complete.
Қайта құру
Қайта конфигурациялау мәселелері комбинаторлық мәселенің шешімдер кеңістігінің байланыстылығына қатысты. Мысалы, графтың екі 4 түстің схемасын бір мезгілде бір төбесінің түсін өзгертетін амалдар арқылы біріктіруге болатынын тексеру, әр қадамда жарамды 4 түстің схемасын сақтай отырып, PSPACE толық мәселе болып табылады, тіпті 3 түстің схемасы үшін дәл осы мәселені полиномиалдық уақытта шешуге болады. Осы салада көптеген басқа мәселелердің PSPACE толықтығын дәлелдеу үшін негіз ретінде сандық Буль формулаларына ұқсас қолданылатын қайта конфигурациялау мәселелерінің тағы бір тобы, белгілі бір шектеулерге сәйкес шектеу графының бағыттарынан тұратын күйлерді және күйден күйге өту амалы бір қанатын бағытын өзгертуден тұрады.
Reconfiguration problems concern the connectivity of a state space of solutions to a combinatorial problem. For instance, testing whether two 4 colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4 coloring, is PSPACE complete, even though the same problem for 3 colorings can be solved in polynomial time. Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE completeness proofs of many other problems in this area, involve nondeterministic constraint logic, in which the states are orientations of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge.