Кіріспе
Шешімдік есептер жиынтығы
In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i. e., in space, where is a polynomial function of Some authors restrict to be a linear function, but most authors instead call the resulting class If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem. A decision problem is if it is in , and every problem in has a polynomial time many one reduction to it. In other words, there is a polynomial time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in
is a strict superset of , , and and is believed to be a strict superset of .
Есептік күрделілік теориясында – бұл детерминистік Тьюринг машинасымен экспоненциалдық кеңістікте, яғни кеңістікте шешілетін барлық шешімдік есептердің жиынтығы, мұнда – полиномдық функция. Кейбір авторлар оны сызықтық функциямен шектейді, бірақ көпшілігі нәтижедегі класты деп атайды. Егер біз недетерминистік машинаны қолдансақ, онда Савич теоремасы бойынша -қа тең класс аламыз. Шешімдік есеп болып есептеледі, егер ол классында болса, және классындағы әрбір есеп оған полиномдық уақытта бір редукцияланады. Басқаша айтқанда, бір есептің мысалдарын екінші есептің мысалдарын бірдей жауаппен түрлендіретін полиномдық уақыт алгоритмі бар. есептері класындағы ең қиын есептер деп есептелуі мүмкін.
In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i. e., in space, where is a polynomial function of Some authors restrict to be a linear function, but most authors instead call the resulting class If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem. A decision problem is if it is in , and every problem in has a polynomial time many one reduction to it. In other words, there is a polynomial time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in
is a strict superset of , , and and is believed to be a strict superset of .
– бұл , , және кластарынан қатаң үлкен класс және класынан да қатаң үлкен деп саналады.
In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i. e., in space, where is a polynomial function of Some authors restrict to be a linear function, but most authors instead call the resulting class If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem. A decision problem is if it is in , and every problem in has a polynomial time many one reduction to it. In other words, there is a polynomial time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in
is a strict superset of , , and and is believed to be a strict superset of .
Проблемалардың мысалдары
Мәселелердің мысалы – екі тұрақты өрнектің әртүрлі тілдерді білдіретінін анықтау мәселесі, мұнда өрнектер төрт оператормен шектеледі: біріктіру, тізбектеме, Клин жұлдызы (өзгерістің нөл немесе одан көп көшірмесі) және квадраттау (өзгерістің екі көшірмесі). Егер Клин жұлдызы алынып тасталса, онда бұл мәселе , , сияқты болады, бірақ ол детерминистік емес Тьюринг машиналары арқылы анықталады, детерминистік Тьюринг машиналары емес. Сондай-ақ, 1980 жылы Л. Берман нақты сандар туралы, тек қосу және салыстыру (бірақ көбейту емес) операцияларын қолданатын кез келген бірінші реттік логикалық тұжырымды тексеру/нақылдау мәселесі болып табылады. Алур және Хензингер уақытты (толық сан) қосып, сызықтық уақыт логикасын кеңейтті және олардың логикасының дұрыстық мәселесі EXPSPACE толық екенін дәлелдеді. Петри желілерінің жабу мәселесі толық. Петри желілерінің қолжетімділік мәселесі ұзақ уақыт бойы қиын екені белгілі болды, бірақ элементар емес екені көрсетілді, сондықтан, бәлкім, ол емес. 2022 жылы ол Акерман толық екені дәлелденді.
Alur and Henzinger extended linear temporal logic with times (integer) and prove that the validity problem of their logic is EXPSPACE complete. The coverability problem for Petri Nets is complete. The reachability problem for Petri nets was known to be hard for a long time, but shown to be nonelementary, so probably not in In 2022 it was shown to be Ackermann complete.
Басқа кластармен қатынасы
белгілі болғандай, , , және олардың үстінен қатаң жиынтық болып табылады. Сонымен қатар, ол , жиынтығының үстінен де қатаң жиынтық болуы күдікті, бірақ бұл әлі белгілі емес.