Есептік күрделіктік теориясындағы мәселелер жиыны

Комплекстік теория: Есептеу қиындықтары, уақыт және жад ресурстары, P классы және Тьюринг машинасы туралы мағлұмат. Теорияны зерттеңіз!

26 мин оқу

100%

Дереккөз: Complexity class — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Компьютерлік күрделілік теориясындағы проблемалар жиынтығы

Компьютерлік күрделілік теориясында күрделілік класы – “бір-бірімен байланысты ресурстарға негізделген күрделілік” компьютерлік проблемалар жиынтығы. Екі ең көп талданатын ресурс – уақыт және жад. Жалпы, күрделілік класы есептеу проблемасының түрі, есептеу моделі және уақыт немесе жад сияқты шектелген ресурс тұрғысынан анықталады. Әсіресе, күрделілік кластарының көпшілігі Тьюринг машинасымен шешілетін шешім проблемаларынан тұрады және олардың уақыт немесе кеңістік (жад) талаптарымен ерекшеленеді. Мысалы, P класы – детерминистік Тьюринг машинасымен полиномиалдық уақытта шешілетін шешім проблемаларының жиынтығы. Дегенмен, басқа типтегі проблемалар (мысалы, санау проблемалары және функция проблемалары) және есептеудің басқа модельдерін пайдалану (мысалы, ықтималдық Тьюринг машиналары, интерактивті дәлелдеу жүйелері, Бульдік тізбектер және кванттық компьютерлер) тұрғысынан анықталған көптеген күрделілік кластары бар. Күрделілік кластары арасындағы қатынастарды зерттеу теориялық компьютерлік ғылымдағы маңызды зерттеу саласы болып табылады. Күрделілік кластарының жиі жалпы иерархиясы болады; мысалы, белгілі бір негізгі уақыт және кеңістік күрделілік кластары бір-бірімен келесідей байланысты: L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆EXPSPACE (мұнда ⊆ қосалқы жиынтық қатынасын білдіреді). Алайда, көптеген қатынастар әлі белгісіз; мысалы, компьютерлік ғылымдағы ең танымал ашық мәселелердің бірі – P класы NP класына тең бола ма деген сұрақ. Кластар арасындағы қатынастар көбінесе есептеудің негізгі мәні туралы сұрақтарға жауап береді. P және NP проблемасы, мысалы, белгісіздік компьютерге есептеу қуатын қоса ма және шешімдері тез тексерілетін проблемаларды тез шешуге бола ма деген сұрақтарға тікелей байланысты.

Өмірбаян

Күрделілік кластары – байланысты есептеу проблемаларының жиынтығы. Олар, белгілі бір есептеу ресурстарына – мысалы, уақытқа немесе жадқа – қатысты, олардың ішіндегі проблемаларды шешудің есептеу қиындығы тұрғысынан анықталады. Күрделілік класының анықтамасы үш нәрседен тұрады: есептеу проблемасының түрі, есептеу моделі және шектелген есептеу ресурсы. Көптеген күрделілік кластары шешім проблемаларынан тұрады, оларды уақыт немесе жад ресурстарымен шектелген Тьюринг машинасымен шешуге болады. Мысалы, P күрделілік класы – детерминистік Тьюринг машинасымен полиномиалдық уақыт ішінде шешілетін шешім проблемаларының жиынтығы ретінде анықталады.

Есептеу проблемалары

Интуитивті түрде, есептеу мәселесі – алгоритм арқылы шешілетін сұрақ. Мысалы, "натурал сан жай сан ба?" – есептеу мәселесі. Есептеу мәселесі математикалық тұрғыдан мәселенің жауаптары жиынтығы ретінде көрсетіледі. Жай сан мысалында, мәселе (оны P деп атайық) жай болатын барлық натурал сандар жиынтығы арқылы бейнеленеді: Есептеу теориясында, осы жауаптар тізбектер түрінде көрсетіледі; мысалы, жай сан мысалында натурал сандар екілік сандарды көрсететін биттер тізбектері түрінде бейнеленуі мүмкін. Осы себепті, есептеу мәселелері жиі тілдермен синоним ретінде қолданылады, себебі биттер тізбектері формальды тілдерді білдіреді (лингвистикадан алынған ұғым); мысалы, P мәселесі NP күрделілік класында екенін айту, P тілі NP-де екенін айтумен мағынасы бірдей.

Шешім қабылдау проблемалары

Теориялық компьютерлік ғылымда ең көп талданатын проблемалар – шешім проблемалары, яғни "иә" немесе "жоқ" деп жауап берілетін сұрақтар түрінде қойылатын проблемалар. Мысалы, жоғарыдағы жай сан мысалы – шешім проблемасы, себебі оны "Бұл сан жай сан ба?" деген "иә" немесе "жоқ" сұрағы арқылы көрсетуге болады. Есептеу теориясы тұрғысынан алғанда, шешім проблемасы – дұрыс алгоритмді іске асыратын компьютер "иә" деп жауап беретін кіріс жолдар жиынтығы ретінде ұсынылады. Жай сан мысалында, бұл жай санды дұрыс анықтайтын алгоритмді іске асыратын компьютерге енгізілгенде, алгоритм "иә, бұл сан жай" деп жауап беретін натурал сандарды білдіретін жолдар жиынтығы. Бұл "иә-жоқ" форматы көбінесе "қабылдау-қабылдамау" деп те аталады; яғни, алгоритм кіріс жолын "қабылдайды", егер шешім проблемасының жауабы "иә" болса, ал жауап "жоқ" болса, "қабылдамайды". Кейбір проблемаларды шешім проблемалары ретінде оңай көрсету мүмкін болмаса да, олар есептеу проблемаларының кең ауқымын қамтиды. Белгілі бір күрделілік кластарымен анықталатын басқа да проблемалар түрлеріне функциялық проблемалар (мысалы, FP), санау проблемалары (мысалы, #P), оптимизация проблемалары және міндеттеме проблемалары жатады ("Басқа проблема түрлері" бөлімін қараңыз).

Есептеу модельдері

"Компьютер" ұғымын нақтылау үшін теориялық компьютерлік ғылымда мәселелер есептеу моделінің аясында талданады. Есептеу модельдері "уақыт" және "жад" сияқты есептеу ресурстарының ұғымдарын дәлдейді. Компьютерлік күрделілік теориясында күрделілік кластары проблемалардың ішкі ресурстық талаптарымен айналысады, физикалық компьютердің құрылысына байланысты талаптармен емес. Мысалы, нақты әлемде әртүрлі компьютерлер бір мәселені шешу үшін әртүрлі уақыт пен жадты қажет етуі мүмкін, себебі олардың жасалу әдісі әртүрлі. Компьютерлердің абстрактілі математикалық бейнелерін ұсына отырып, есептеу модельдері негізгі принциптерді түсінуге кедергі келтіретін нақты әлемнің артық күрделіліктерін (процессор жылдамдығының айырмашылығы сияқты) абстрактілендіреді. Ең көп қолданылатын есептеу моделі – Тьюринг машинасы. Басқа модельдер де бар және көптеген күрделілік кластары олар арқылы анықталады (қараңыз, "Компьютерлік есептеудің басқа модельдері" бөлімі), бірақ Тьюринг машинасы күрделілік кластарының көп бөлігін анықтау үшін қолданылады. Тьюринг машинасымен, секунд сияқты стандартты уақыт бірліктерін (физикалық аппараттық жылдамдықтан жұмыс уақытын ажырату мүмкін емес ететін) және байттар сияқты стандартты жад бірліктерін пайдаланудың орнына, уақыт ұғымы Тьюринг машинасы мәселені шешу үшін жасайтын элементарлық қадамдар саны ретінде абстрактілендіріледі, ал жад ұғымы машина таспасында қолданылатын жасушалар саны ретінде абстрактілендіріледі. Бұл туралы төменде толығырақ түсіндіріледі. Блум аксиомаларын нақты есептеу моделін көрсетпей күрделілік кластарын анықтау үшін де пайдалануға болады, бірақ бұл тәсіл күрделілік теориясында жиі қолданылмайды.

Детерминистік Тьюринг машиналары

Тьюринг машинасы – жалпы есептеу машинасының математикалық моделі. Бұл күрделілік теориясында ең көп қолданылатын модель, себебі ол есептеудің кез келген басқа моделі сияқты қуатты және математикалық талдау оңай деп есептеледі. Маңыздысы, егер белгілі бір мәселені шешетін алгоритм болса, онда сол мәселені шешетін Тьюринг машинасы да бар деп есептеледі (бұл Чёрч-Тьюринг тезисі деп аталады); бұл дегеніміз, әрбір алгоритмді Тьюринг машинасы ретінде көрсетуге болады. Механикалық тұрғыдан алғанда, Тьюринг машинасы (ТМ) шексіз ұзын таспа жолағында орналасқан символдарды (әдетте 0 және 1 биттерімен шектеледі, бұл нақты компьютерлерге интуитивті байланыс жасайды) манипуляциялайды. ТМ бір-бірден таспаның басы арқылы оқи алады және жаза алады. Операция толықтай элементар нұсқаулардың шекті жиынтығымен анықталады, мысалы, "42-ші күйде, егер көрсетілген символ 0 болса, 1-ді жазыңыз; егер көрсетілген символ 1 болса, 17-ші күйге ауысыңыз; 17-ші күйде, егер көрсетілген символ 0 болса, 1-ді жазыңыз және 6-шы күйге ауысыңыз". Тьюринг машинасы тек қана таспадағы кіріс тізбегімен басталады және барлық басқа жерде бос орындар болады. ТМ егер ол белгіленген қабылдау күйіне кірсе, кірісті қабылдайды және егер ол бас тарту күйіне кірсе, кірісті қабылдамайды. Детерминистік Тьюринг машинасы (ДТМ) – Тьюринг машинасының ең негізгі түрі. Ол өзінің болашақ іс-әрекеттерін анықтау үшін ережелердің белгіленген жиынтығын қолданады (осы себепті ол "детерминистік" деп аталады). Есептеулік проблеманы кейін белгілі бір Тьюринг машинасы қабылдайтын кіріс тізбелерінің жиынтығы ретінде Тьюринг машинасы тұрғысынан анықтауға болады. Мысалы, жоғарыда келтірілген жай сан табу мәселесі – бұл жай санды дұрыс тексертін алгоритмді орындайтын Тьюринг машинасы қабылдайтын тізбектер жиынтығы (натурал сандарды білдіреді). Тьюринг машинасы тілді таниды деп айтылады ("проблема" және "тіл" есептеу қабілеті мен күрделілік теориясында көбінесе синонимдер) егер ол тілдегі барлық кірісті қабылдаса және тілді шешеді деп айтылады, егер ол тілдегі емес кірістерді де бас тартса (белгілі бір кірістер Тьюринг машинасының мәңгілікке жұмыс істеуі мүмкін, сондықтан шешілу қабілеті Тьюринг машинасының барлық кірістерде тоқтауы керек деп тану қабілетіне қосымша шектеу қояды). Мәселені "шешейтін" Тьюринг машинасы әдетте тілді шешеді дегенді білдіреді. Тьюринг машиналары "уақыт" және "кеңістік" туралы интуитивті түсініктерді қалыптастыруға мүмкіндік береді. Белгілі бір кіріс бойынша ТМ-нің уақыт күрделілігі – бұл Тьюринг машинасының қабылдау немесе қабылдамау күйіне жету үшін атқаратын элементарлық қадамдардың саны. Кеңістік күрделілігі – бұл оның таспасындағы ұяшықтардың саны, оны қабылдау немесе қабылдамау күйіне жету үшін пайдаланады.

A Turing machine is a mathematical model of a general computing machine. It is the most commonly used model in complexity theory, owing in large part to the fact that it is believed to be as powerful as any other model of computation and is easy to analyze mathematically. Importantly, it is believed that if there exists an algorithm that solves a particular problem then there also exists a Turing machine that solves that same problem (this is known as the Church–Turing thesis); this means that it is believed that every algorithm can be represented as a Turing machine. Mechanically, a Turing machine (TM) manipulates symbols (generally restricted to the bits 0 and 1 to provide an intuitive connection to real life computers) contained on an infinitely long strip of tape. The TM can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6". The Turing machine starts with only the input string on its tape and blanks everywhere else. The TM accepts the input if it enters a designated accept state and rejects the input if it enters a reject state. The deterministic Turing machine (DTM) is the most basic type of Turing machine. It uses a fixed set of rules to determine its future actions (which is why it is called "deterministic"). A computational problem can then be defined in terms of a Turing machine as the set of input strings that a particular Turing machine accepts. For example, the primality problem from above is the set of strings (representing natural numbers) that a Turing machine running an algorithm that correctly tests for primality accepts. A Turing machine is said to recognize a language (recall that "problem" and "language" are largely synonymous in computability and complexity theory) if it accepts all inputs that are in the language and is said to decide a language if it additionally rejects all inputs that are not in the language (certain inputs may cause a Turing machine to run forever, so decidability places the additional constraint over recognizability that the Turing machine must halt on all inputs). A Turing machine that "solves" a problem is generally meant to mean one that decides the language. Turing machines enable intuitive notions of "time" and "space". The time complexity of a TM on a particular input is the number of elementary steps that the Turing machine takes to reach either an accept or reject state. The space complexity is the number of cells on its tape that it uses to reach either an accept or reject state.

Детерминистік емес Тьюринг машиналары

Детерминистік Тьюринг машинасы (ДТМ) — детерминистік емес Тьюринг машинасының (НТМ) бір түрі. Интуитивті тұрғыдан алғанда, НТМ — бұл белгілі бір күйден бастап, болашақтағы мүмкін әрекеттердің бірнеше бағытын зерттеуге және қабылдайтын бағытын "таңдауға" (егер мұндай бағыт болса) қабілеті бар кәдімгі Тьюринг машинасы. Яғни, ДТМ есептеудің тек бір бағытын орындаса, НТМ-ді есептеу ағашы ретінде көзге елестете беруге болады, ол әр қадамда көптеген мүмкін есептеу жолдарына тармақталады (суретті қараңыз). Егер ағаштың кем дегенде бір тармағы "қабылдау" шартымен тоқтаса, онда НТМ кірісті қабылдайды. Осылайша, НТМ-ді барлық есептеу мүмкіндіктерін бір уақытта, параллель түрде зерттеп, қабылдаушы бағытты таңдап алу ретінде қарастыруға болады. НТМ-дер физикалық жағынан іске асырылатын модельдер емес, олар тек теориялық тұрғыдан қызықты абстрактілі машиналар, олар бірқатар қызықты күрделілік кластарын тудырады (олардың көпшілігі физикалық жағынан іске асырылатын эквивалентті анықтамаларға ие). НТМ-нің уақыт күрделілігі — НТМ есептеуінің кез келген тармағында қолданатын қадамдардың максималды саны. Сол сияқты, НТМ-нің кеңістік күрделілігі — НТМ есептеуінің кез келген тармағында пайдаланатын жад ұяшықтарының максималды саны. ДТМ-ді нон-детерминизмнің күшін пайдаланбайтын НТМ-нің ерекше жағдайы ретінде қарастыруға болады. Сондықтан, ДТМ арқылы орындалатын кез келген есептеуді эквивалентті НТМ арқылы да орындауға болады. Кез келген НТМ-ді ДТМ арқылы симуляциялау да мүмкін (ДТМ жай ғана әрбір мүмкін есептеу бағытын бірінен кейін бірі есептейді). Осылайша, екеуі де есептеу мүмкіндіктері тұрғысынан тең. Дегенмен, НТМ-ді ДТМ арқылы симуляциялау көбінесе көп уақыт және/немесе жад ресурстарын қажет етеді; көрініп тұрғандай, есептеу мәселелерінің белгілі бір кластары үшін бұл баяулаудың маңыздылығы есептеу күрделілігі теориясындағы маңызды сұрақ болып табылады.

Ресурс шектері

Күрделілік кластары есептеу мәселелерін олардың ресурстық талаптары бойынша топтастырады. Мұны істеу үшін есептеу проблемалары оларды шешу үшін ең тиімді алгоритмге қажетті ресурстардың ең жоғары мөлшерімен белгіленеді. Нақтырақ айтқанда, күрделілік кластары кіріс мөлшері артқан сайын нақты есептеу мәселелерін шешуге қажетті ресурстардың өсу қарқынымен айналысады. Мысалы, P күрделілік класындағы мәселелерді шешуге кететін уақыт мөлшері кіріс мөлшері артқан сайын полиномиалдық жылдамдықпен өседі, бұл EXPTIME экспоненциалдық күрделілік класындағы мәселелермен салыстырғанда салыстырмалы түрде баяу (немесе дәлірек айтқанда, P класына жатпайтын EXPTIME класындағы мәселелер үшін). Күрделілік кластарын зерттеудің мақсаты – есептеу мәселелерін шешуге қажетті туа біткен күрделілікті түсіну. Сондықтан күрделілік теориясымен айналысатындар мәселенің ең кіші күрделілік класын табуға тырысады және ең тиімді алгоритмді қолдану арқылы есептеу мәселесінің қай кластың ішіне жататынын анықтауға көңіл бөледі. Мысалы, белгілі бір мәселені экспоненциалдық уақытта шешетін алгоритм болуы мүмкін, бірақ егер осы мәселені шешудің ең тиімді алгоритмі полиномиалдық уақытта жұмыс істесе, онда осы мәселенің туа біткен уақыт күрделілігі полиномиалдық деп сипаттау дұрыс.

Уақыт шегі

Тьюринг машинасының моделіне қатысты алгоритмнің уақыт күрделілігі – берілген кіріс мөлшері үшін алгоритмді іске асыруға Тьюринг машинасына қажетті қадамдар саны. Формальды түрде, Тьюринг машинасымен жүзеге асырылған алгоритмнің уақыт күрделілігі функциясы ретінде анықталады, мұнда – кез келген ұзындығы кіріс үшін қадамдардың максималды саны. Есептеу күрделілігі теориясында теориялық компьютер ғалымдары нақты орындалу уақытының мәніне қарағанда уақыт күрделілігі функциясының жалпы класына көбірек көңіл бөледі. Мысалы, уақыт күрделілігі функциясы полиномдық па? Логарифмдік функция ма? Экспоненциалдық функция ма? Әлде басқа функция ма?

Ғарыш шекаралары

Тьюринг машинасының моделіне қатысты алгоритмнің кеңістіктік күрделілігі – берілген кіріс мөлшері үшін алгоритмді іске қосуға қажет Тьюринг машинасының таспасындағы жасушалардың саны. Формальды түрде, Тьюринг машинасымен жүзеге асырылған алгоритмнің кеңістіктік күрделілігі функция ретінде анықталады, мұнда – кез келген ұзындығы болған кіріс үшін қолданылатын жасушалардың максималды саны.

Негізгі анықтамалар

Күрделілік сыныптары көбінесе DTIME және NTIME (уақыт күрделілігі үшін) және DSPACE және NSPACE (кеңістік күрделілігі үшін) деп аталатын күрделілік сыныптарының ұсақ жиынтықтарын пайдалана отырып анықталады. Үлкен О белгісін қолдану арқылы олар келесідей анықталады: Уақыт күрделілігі класы – бұл белгілі бір уақыт ішінде детерминистік Тьюринг машинасы шешетін барлық проблемалардың жиынтығы. Уақыт күрделілігі класы – бұл белгілі бір уақыт ішінде нон-детерминистік Тьюринг машинасы шешетін барлық проблемалардың жиынтығы. Кеңістік күрделілігі класы – бұл белгілі бір кеңістік көлемінде детерминистік Тьюринг машинасы шешетін барлық проблемалардың жиынтығы. Кеңістік күрделілігі класы – бұл белгілі бір кеңістік көлемінде нон-детерминистік Тьюринг машинасы шешетін барлық проблемалардың жиынтығы.

P және NP

P – детерминистік Тьюринг машинасымен полиномиалдық уақытта шешілетін мәселелер класы, ал NP – детерминистік емес Тьюринг машинасымен полиномиалдық уақытта шешілетін мәселелер класы. Немесе, формальдырақ айтқанда, P – детерминистік компьютермен «жылдам» немесе «тиімді» шешілетін мәселелер класы, себебі P класындағы мәселені шешудің уақыт күрделілігі кіріс мөлшерімен салыстырмалы түрде баяу өседі. NP класының маңызды ерекшелігі – оны эквивалентті түрде шешімдері детерминистік Тьюринг машинасымен полиномиалдық уақытта тексерілетін мәселелер класы ретінде анықтауға болады. Яғни, тіл NP класына жатады, егер детерминистік полиномиалдық уақытты Тьюринг машинасы (верификатор деп аталады) кіріс ретінде бір жол мен полиномиалдық өлшемдегі сертификат жолын қабылдап, егер жол тілде болса, қабылдаса, ал тілде болмаса, қабылдамаса. Интуитивті түрде, сертификат кіріс жолы тілде екенін дәлелдейтін құжат болып табылады. Формальды түрде: NP – бұл тілдер класы, он үшін полиномиалдық уақытты детерминистік Тьюринг машинасы және полином бар, сонда барлық жағдайларда , егер және тек қана егер кейбір болатын болса, онда қабылдайды. Нендетерминистік анықтама мен верификатор анықтамасы арасындағы осы тепе-теңдік нендетерминизм мен шешімді тексеру арасындағы маңызды байланысты көрсетеді. Бұдан әрі, бұл тілдің NP класына жататынын дәлелдеудің пайдалы әдісін ұсынады – жарамды сертификатты анықтап, оның полиномиалдық уақытта тексерілетінін көрсету жеткілікті.

P және NP проблемасы

Кейбір проблемаларды тиімді шешу класы мен олардың шешімдерін тиімді тексеру класы арасында көзге көрінетін айырмашылық болғанымен, P және NP шындығында компьютерлік ғылымдағы ең әйгілі шешілмеген мәселелердің бірі – P және NP мәселесінің ортасында тұр. PNP (интуитивті түсіндірсек, детерминистік Тьюринг машиналары – бұл өз детерминизмін пайдаланбайтын недетерминистік Тьюринг машиналарының кіші класы; немесе тексеруші анықтамасы бойынша, P – бұл полиномиалдық уақытта тексерушісіне тек бос жол сертификат ретінде жеткілікті болатын проблемалар класы), бірақ NP, P-ден қатаң үлкен екендігі әлі белгісіз. Егер P=NP болса, онда недетерминизм, мәселенің шешімін жылдам табу мүмкіндігі тұрғысынан детерминизмге қарағанда қосымша есептеу күші бермейді; яғни, есептеудің барлық мүмкін тармақтарын қарастыру, тек бір тармақты қарастыруға қарағанда полиномиалдық жылдамдықпен ғана артықшылық береді. Бұдан әрі, егер мәселенің нақты мысалы үшін дәлел болса және осы дәлелдің дұрыстығын жылдам тексеруге болады (яғни, егер мәселе NP класына жатса), онда осы дәлелді жылдам құрастыра алатын алгоритм де бар (яғни, мәселе P класына жатады). Дегенмен, компьютерлік ғалымдардың көпшілігі PNP деп санайды, ал бүгінде қолданылатын көптеген криптографиялық схемалар PNP болжамына негізделген.

EXPTIME және NEXPTIME

EXPTIME (кейде EXP деп қысқартылады) – детерминистік Тьюринг машинасы экспоненциалды уақытта шеше алатын шешімдер класы, ал NEXPTIME (кейде NEXP деп қысқартылады) – детерминистік емес Тьюринг машинасы экспоненциалды уақытта шеше алатын шешімдер класы. Немесе, формальдырақ айтқанда, EXPTIME – P класының қатаң үстімдік жиыны, ал NEXPTIME – NP класының қатаң үстімдік жиыны. Бұдан әрі, EXPTIME, NEXPTIME кластарын қамтиды. Бұл қатыстың дұрыс екені белгісіз, бірақ егер P=NP болса, онда EXPTIME, NEXPTIME кластары тең болуы керек.

L және NL

Логарифмдік уақыт күрделілігі сыныптарын анықтау мүмкін болса да, бұл өте тар сыныптар, себебі сызықтық емес уақыт Тьюринг машинасына кірістің барлығын оқуға мүмкіндік бермейді (өйткені ). Дегенмен, логарифмдік кеңістікте шешілетін маңызды мәселелер бар. Бұл сыныптарды анықтау үшін екі ленталы Тьюринг машинасы қажет, осылайша машина кірістің барлығын сақтай алады (екі ленталы Тьюринг машинасының есептеу мүмкіндігі бір ленталы Тьюринг машинасымен тең екенін көрсетуге болады). Екі ленталы Тьюринг машинасының моделінде бір лента – тек оқуға арналған кіріс лентасы. Екіншісі – жұмыс лентасы, ол оқу және жазу мүмкіндігін береді және Тьюринг машинасы есептеулерді осы лентада жүргізеді. Тьюринг машинасының кеңістік күрделілігі жұмыс лентасында қолданылған жасушалар санымен өлшенеді. L (кейде LOGSPACE деп толықтырылады) – детерминистік Тьюринг машинасымен логарифмдік кеңістікте шешілетін мәселелер класы, ал NL (кейде NLOGSPACE деп толықтырылады) – детерминистік емес Тьюринг машинасымен логарифмдік кеңістікте шешілетін мәселелер класы. Немесе, формальды түрде, бұл белгілі, бірақ бұл қатынастардың кез келгенінің дұрыс екендігі әлі белгісіз.

PSPACE және NPSPACE

PSPACE және NPSPACE күрделілік сыныптары P және NP-ге кеңістіктегі аналогтар болып табылады. Яғни, PSPACE – детерминистік Тьюринг машинасымен полиномдық кеңістікте шешілетін мәселелер класы, ал NPSPACE – детерминистік емес Тьюринг машинасымен полиномдық кеңістікте шешілетін мәселелер класы. Әрі қысқаша айтқанда, P=NP екендігі әлі белгісіз, бірақ Савич теоремасы PSPACE=NPSPACE екенін көрсетті. Сонымен қатар, PPSPACE белгілі, себебі Тьюринг машинасының таспасындағы бір жасуға бір уақыт бірлігі жұмсалатынын ескерсек, полиномдық уақытта жұмыс істейтін Тьюринг машинасы тек полиномдық мөлшердегі жасуларға ғана жаза алады. P класы PSPACE класынан кішірек болуы мүмкін деп болжанады, бірақ бұл әлі дәлелденбеді.

EXPSPACE және NEXPSPACE

EXPSPACE және NEXPSPACE күрделілік сыныптары EXPTIME және NEXPTIME-нің кеңістіктік аналогтары болып табылады. Яғни, EXPSPACE – детерминистік Тьюринг машинасымен экспоненциалдық кеңістікте шешілетін мәселелер класы, ал NEXPSPACE – детерминистік емес Тьюринг машинасымен экспоненциалдық кеңістікте шешілетін мәселелер класы. Немесе формальдырақ айтқанда,

Савич теоремасы EXPSPACE=NEXPSPACE екенін көрсетті. Бұл сынып өте кең: ол PSPACE, NP және P-нің қатаң үстел жиыны болып табылады және EXPTIME-нің қатаң үстел жиыны деп саналады.

Жабылу

Күрделілік кластарының әртүрлі жабылу қасиеттері бар. Мысалы, шешім кластары жоққа шығару, біріктіру, ажырату немесе тіпті барлық Буль операциялары бойынша жабық болуы мүмкін. Сонымен қатар, олар әртүрлі квантификация схемалары бойынша да жабық болуы мүмкін. P, мысалы, барлық Буль операциялары бойынша және полиномдық өлшемді домендер бойынша квантификация арқылы жабық. Жабылу қасиеттері кластарды ажыратуға көмектесе алады – екі күрделілік класын ажыратудың бір жолы – бір класта бар, бірақ екіншісінде жоқ жабылу қасиетін табу. Жоққа шығару бойынша жабылмаған әрбір X класы үшін co X толықтыру класы бар, ол X класына кіретін тілдердің толықтыруларынан тұрады (яғни co X = X). Мысалы, co NP – маңызды толықтыру күрделілік класы және co NP=NP мәселесі шешілмеген күйде тұр. Жабылу қасиеттері – көптеген күрделілік кластарының осылай анықталуының басты себептерінің бірі. Мысалы, (яғни сызықтық уақытта) шешілетін мәселені және ең жақсы жағдайда уақытта шешілетін мәселені қарастырайық. Бұл екі мәселе де P класына жатады, бірақ екіншісінің орындалу уақыты кіріс мөлшері артқан сайын біріншісінен әлдеқайда жылдам өседі. "Тиімді шешілетін" мәселелер класын барлық полиномдардың орнына, мысалы, кішірек полиномдық шектеулерді қолдану арқылы анықтау жақсырақ болар ма, бұл мұндай үлкен айырмашылықтарға мүмкіндік береді? Деген сұрақ туындайды. Алайда, барлық полиномдар жиыны – қосу, көбейту және композиция бойынша жабық болатын сызықтық функцияларды қамтитын функциялардың ең кіші класы (мысалы, – полином, бірақ ). Бір тиімді алгоритмді екінші тиімді алгоритммен біріктіргенде де тиімді болып саналуы керек болғандықтан, полиномдар – "тиімді алгоритмдердің" композициясын қамтамасыз ететін ең кіші класс. (P анықтамасының да пайдалы екенін ескеріңіз, себебі тәжірибеде P класындағы дерлік барлық проблемалар іс жүзінде пайдалы және төменгі дәрежелі полиномдық орындалу уақытына ие, ал P класынан тыс, бірақ практикалық тұрғыдан пайдалы барлық проблемалар үшін шағын экспоненциалдық орындалу уақыты бар алгоритмдер белгілі емес, яғни орындалу уақыты 1-ге жақын.)

Complexity classes have a variety of closure properties. For example, decision classes may be closed under negation, disjunction, conjunction, or even under all Boolean operations. Moreover, they might also be closed under a variety of quantification schemes. P, for instance, is closed under all Boolean operations, and under quantification over polynomially sized domains. Closure properties can be helpful in separating classes—one possible route to separating two complexity classes is to find some closure property possessed by one class but not by the other. Each class X that is not closed under negation has a complement class co X, which consists of the complements of the languages contained in X (i. e. co X= X ). co NP, for instance, is one important complement complexity class, and sits at the center of the unsolved problem over whether co NP=NP. Closure properties are one of the key reasons many complexity classes are defined in the way that they are. Take, for example, a problem that can be solved in time (that is, in linear time) and one that can be solved in, at best, time. Both of these problems are in P, yet the runtime of the second grows considerably faster than the runtime of the first as the input size increases. One might ask whether it would be better to define the class of "efficiently solvable" problems using some smaller polynomial bound, like , rather than all polynomials, which allows for such large discrepancies. It turns out, however, that the set of all polynomials is the smallest class of functions containing the linear functions that is also closed under addition, multiplication, and composition (for instance, , which is a polynomial but ). Since we would like composing one efficient algorithm with another efficient algorithm to still be considered efficient, the polynomials are the smallest class that ensures composition of "efficient algorithms". (Note that the definition of P is also useful because, empirically, almost all problems in P that are practically useful do in fact have low order polynomial runtimes, and almost all problems outside of P that are practically useful do not have any known algorithms with small exponential runtimes, i. e. with runtimes where is close to 1.)

Төлемдерді азайту

Көптеген күрделік кластары редукция түсінігі арқылы анықталады. Редукция – бір мәселені екінші мәселеге түрлендіру, яғни редукция бір мәселенің кіріс деректерін алып, оларды екінші мәселенің кіріс деректеріне айналдырады. Мысалы, сіз ондық санау жүйесіндегі қарапайым қосуды екілік санау жүйесіндегі қосуға түрлендіру арқылы 5 пен 7 сандарын екілік санау жүйесіндегі 101 және 111 сандарына айналдыруға болады (мысалы, 5+7 → 101+111). Формальды түрде, егер барлық үшін , егер және тек егер болса, онда функция бар болса, мәселе мәселеге редукцияланады.
Жалпы, редукциялар бір мәселенің екінші мәселеден кем емес қиындығын көрсету үшін қолданылады. Сондықтан біз көбінесе полиномдық уақытта редукция қолдануға қызығушымыз, себебі кез келген мәселе, егер ол тиімді түрде екінші мәселеге редукцияланса, онда ол екінші мәселеден қиын болмайды. Формальды түрде, егер полиномдық уақытта есептелетін функция бар болса, онда мәселе мәселеге полиномдық уақытта редукцияланады, егер барлық үшін , егер және тек егер болса.
Редукциялар әртүрлі жолдармен анықталуы мүмкін екенін ескеріңіз. Кездесетін редукциялардың түрлері – Кук редукциясы, Карп редукциясы және Левин редукциясы. Олар ресурс шектеулеріне байланысты, мысалы полиномдық уақытты редукция және логарифмдік кеңістікті редукция сияқты өзгеріп отыруы мүмкін.

Қаттылығы

Кемітулер күрделілік класы үшін проблеманың қиындығын түсіндіреді. Егер C проблемалар класындағы кез келген проблема полиномиалдық уақытта берілген проблемаға келтірілсе, онда ол проблема C класы үшін қиын болып саналады. С-дегі ешбір проблема берілгеннен қиын емес, себебі берілген проблеманы шеше алатын алгоритм C класындағы кез келген проблеманы полиномиалдық уақыттан аспайтын баяулаумен шешуге мүмкіндік береді. Атап айтқанда, NP үшін қиын болатын проблемалар жиынтығы NP-қиын проблемалар жиынтығы деп аталады.

Толықтығы

Егер бір мәселе C үшін қиын болса және сол C класында жатса, онда ол C үшін толық деп аталады. Бұл C класындағы ең қиын мәселе екенін білдіреді (өйткені C класында одан да қиын немесе тең қиын проблемалар болуы мүмкін, дәлірек айтқанда, ол C класындағы ең қиын проблемалармен бірдей қиындық деңгейінде). Ерекше маңызға ие – NP-толық проблемалар класы, NP класындағы ең қиын проблемалар. NP класындағы барлық проблемаларды полиномиалдық уақытта NP-толық проблемаларға келтіруге болады, сондықтан полиномиалдық уақытта шешілетін NP-толық проблеманы табу P = NP екенін көрсетер еді.

Савич теоремасы

Савич теоремасы детерминистік және детерминистік емес кеңістік ресурстары арасындағы қатынасты белгілейді. Ол егер детерминистік емес Тьюринг машинасы бір мәселені кеңістік көлемін пайдаланып шеше алса, онда детерминистік Тьюринг машинасы сол мәселені кеңістік көлемінде, яғни кеңістік көлемінің квадратында шеше алатынын көрсетеді. Формальды түрде, Савич теоремасы былай тұжырымдайды: кез келген үшін,

Савич теоремасының маңызды салдары – PSPACE = NPSPACE (өйткені полиномның квадраты да полином болып қалады) және EXPSPACE = NEXPSPACE (өйткені экспонентаның квадраты да экспонента болып қалады). Бұл қатынастар детерминизммен салыстырғанда нондетерминизмнің мүмкіндіктері туралы маңызды сұрақтарға жауап береді. Атап айтқанда, Савич теоремасы детерминистік емес Тьюринг машинасы полиномдық кеңістікте шеше алатын кез келген мәселені детерминистік Тьюринг машинасы да полиномдық кеңістікте шеше алатынын көрсетеді. Сол сияқты, детерминистік емес Тьюринг машинасы экспоненциалдық кеңістікте шеше алатын кез келген мәселені детерминистік Тьюринг машинасы да экспоненциалдық кеңістікте шеше алады.

Күрделілік кластары

Фундаменталды кездейсоқ уақыт күрделілігі сыныптары: ZPP, RP, co RP, BPP және PP. Ең қатаң сынып - ZPP (нөлдік қателік ықтималдығы бар полиномиялық уақыт), яғни қателік ықтималдығы 0 болатын ықтималдық Тьюринг машинасымен полиномиялық уақытта шешілетін проблемалар класы. Бұл, интуитивті түрде, ықтималдық проблемалардың ең қатаң класы, себебі ол ешқандай қателікке жол бермейді. Сәл бос сынып - RP (кездейсоқ полиномиялық уақыт), ол тілге жатпайтын тізбектер үшін қателік жібермейді, бірақ тілге жататын тізбектер үшін шектелген қателікке мүмкіндік береді. Формальды түрде, тіл RP класына жатады, егер ықтималдық полиномиялық уақыт Тьюринг машинасы болса, онда тілге жатпайтын тізбектер үшін ол әрқашан қабылдамайды, ал тілге жататын тізбектер үшін кем дегенде 1/2 ықтималдықпен қабылдайды. co RP класы да осылай анықталады, бірақ рөлдер ауыстырылады: тілге жататын тізбектер үшін қателікке жол берілмейді, бірақ тілге жатпайтын тізбектер үшін рұқсат етіледі. Бірге алғанда, RP және co RP кластары бір жақты қателікпен ықтималдық Тьюринг машиналарымен шешілетін барлық проблемаларды қамтиды. Қателік талаптарын екі жақты қателікке жол беру үшін жеңілдету BPP (шектелген қателік ықтималдығы бар полиномиялық уақыт) класын береді, яғни қателік ықтималдығы 1/3-тен кем (тілге жататын және жатпайтын тізбектер үшін) полиномиялық уақытта ықтималдық Тьюринг машинасымен шешілетін проблемалар класы. BPP – ықтималдық күрделілік сыныптарының ең практикалық маңыздысы, себебі BPP класындағы проблемаларға нақты компьютерлерде жылдам орындалатын тиімді кездейсоқ алгоритмдер бар. BPP сонымен қатар компьютерлік ғылымдағы маңызды, әлі шешілмеген P=BPP мәселесінің ортасында тұр, егер бұл дұрыс болса, онда кездейсоқтық компьютерлердің есептеу қуатын арттырмайды, яғни кез келген ықтималдық Тьюринг машинасы детерминистік Тьюринг машинасымен полиномиялық уақыттан аспайтын баяулаумен симуляциялана алады. Тиімді шешілетін ықтималдық проблемалардың ең кең класы PP (ықтималдық полиномиялық уақыт), яғни барлық тізбектер үшін 1/2-ден кем қателік ықтималдығымен полиномиялық уақытта ықтималдық Тьюринг машинасымен шешілетін тілдер жиынтығы. ZPP, RP және co RP – барлығы BPP-нің кіші жиынтығы, ал BPP өз кезегінде PP-нің кіші жиынтығы. Мұның себебі интуитивті: нөлдік қателікке және тек бір жақты қателікке жол беретін кластар екі жақты қателікке жол беретін кластың ішінде болады, ал PP жай ғана BPP қателік ықтималдығын жеңілдетеді. ZPP, RP және co RP арасындағы байланыс мынадай: ZPP – RP және co RP кластарының тоғысқан бөлігі, яғни ZPP-ге RP және co RP кластарының екеуіне де жататын проблемалар кіреді. Бұл, интуитивті түрде, RP және co RP тек бір жақты қателікке жол беретінінен туындайды: co RP тілге жататын тізбектер үшін қателікке жол бермейді, ал RP тілге жатпайтын тізбектер үшін қателікке жол бермейді. Сондықтан, егер проблема RP және co RP кластарына жатса, онда тілге жататын және жатпайтын тізбектер үшін қателік болмауы керек (яғни ешқандай қателік болмауы керек), бұл ZPP-нің анықтамасымен сәйкес келеді. Маңызды кездейсоқ кеңістік күрделілігі кластарына BPL, RL және RLP жатады.

The fundamental randomized time complexity classes are ZPP, RP, co RP, BPP, and PP. The strictest class is ZPP (zero error probabilistic polynomial time), the class of problems solvable in polynomial time by a probabilistic Turing machine with error probability 0. Intuitively, this is the strictest class of probabilistic problems because it demands no error whatsoever. A slightly looser class is RP (randomized polynomial time), which maintains no error for strings not in the language but allows bounded error for strings in the language. More formally, a language is in RP if there is a probabilistic polynomial time Turing machine such that if a string is not in the language then always rejects and if a string is in the language then accepts with a probability at least 1/2. The class co RP is similarly defined except the roles are flipped: error is not allowed for strings in the language but is allowed for strings not in the language. Taken together, the classes RP and co RP encompass all of the problems that can be solved by probabilistic Turing machines with one sided error. Loosening the error requirements further to allow for two sided error yields the class BPP (bounded error probabilistic polynomial time), the class of problems solvable in polynomial time by a probabilistic Turing machine with error probability less than 1/3 (for both strings in the language and not in the language). BPP is the most practically relevant of the probabilistic complexity classes—problems in BPP have efficient randomized algorithms that can be run quickly on real computers. BPP is also at the center of the important unsolved problem in computer science over whether P=BPP, which if true would mean that randomness does not increase the computational power of computers, i. e. any probabilistic Turing machine could be simulated by a deterministic Turing machine with at most polynomial slowdown. The broadest class of efficiently solvable probabilistic problems is PP (probabilistic polynomial time), the set of languages solvable by a probabilistic Turing machine in polynomial time with an error probability of less than 1/2 for all strings. ZPP, RP and co RP are all subsets of BPP, which in turn is a subset of PP. The reason for this is intuitive: the classes allowing zero error and only one sided error are all contained within the class that allows two sided error, and PP simply relaxes the error probability of BPP. ZPP relates to RP and co RP in the following way: That is, ZPP consists exactly of those problems that are in both RP and co RP. Intuitively, this follows from the fact that RP and co RP allow only one sided error: co RP does not allow error for strings in the language and RP does not allow error for strings not in the language. Hence, if a problem is in both RP and co RP, then there must be no error for strings both in and not in the language (i. e. no error whatsoever), which is exactly the definition of ZPP. Important randomized space complexity classes include BPL, RL, and RLP.

Интерактивті дәлелдеу жүйелері

Бірқатар күрделілік сыныптары интерактивті дәлелдеу жүйелерін пайдалану арқылы анықталады. Интерактивті дәлелдеулер NP күрделілік класының дәлелдеу анықтамасын кеңейтеді және криптография, жуықтау алгоритмдері және формалды тексеру салаларына жаңа түсініктер ұсынады. Интерактивті дәлелдеу жүйелері – екі тараптың арасындағы хабар алмасу арқылы есептеуді модельдейтін абстрактілі машиналар: дәлелдеуші және тексеруші. Тараптар хабар алмасу арқылы өзара әрекеттеседі, ал жүйе кіріс жолын қабылдайды, егер тексеруші дәлелдеушіден алған хабарлар негізінде кірісті қабылдауға шешім қабылдаса. Дәлелдеушінің есептеу қуаты шексіз, ал тексерушінің есептеу қуаты шектеулі (интерактивті дәлелдеу жүйелерінің стандартты анықтамасы тексерушінің уақыты полиномдық түрде шектелгенін көрсетеді). Дегенмен, дәлелдеушіге сенімсіздік танытылады (бұл, егер есептеу қуаты шексіз дәлелдеуші тілдегі жолдың болуын анықтап, содан кейін тексерушіге сенімді «Иә» немесе «Жоқ» жауабын жіберсе, барлық тілдерді дәлелдеу жүйесімен оңай тануға кедергі келтіреді), сондықтан тексеруші дәлелдеушіден сұрақтар арқылы «сұрау салу» арқылы тексеруі керек, жол тілде бар екеніне жоғары деңгейде сенімділікке жеткен жағдайда ғана қабылдайды.

Бульдік схемалар

Тьюринг машинасына баламалы есептеу моделі — Бульдік схема, қазіргі заманғы компьютерлерде қолданылатын цифрлық схемалардың қарапайымдалған моделі. Бұл модель теориядағы есептеу мен практикадағы есептеу арасындағы интуитивті байланысты қамтамасыз етеді, сонымен қатар ол біркелкі емес есептеудің табиғи моделі болып табылады (бір проблеманың әртүрлі кіріс өлшемдері әртүрлі алгоритмдерді қолданатын есептеу). Формальды түрде Бульдік схема — бұл бағытталған ациклдік граф, онда қабырғалар сымдарды (0 және 1 биттік мәндерін тасымалдайтын) білдіреді, кіріс биттері бастапқы төбелермен (кіріспеуші қабырғалары жоқ төбелермен) көрсетіледі, ал барлық бастапқы емес төбелер логикалық қақпаларды (әдетте AND, OR және NOT қақпаларын) білдіреді. Бір логикалық қақпа шығыс қақпасы деп белгіленеді және есептеудің соңына жатады. Кіріс/шығыс мінез-құлқы кіріс айнымалылары бар схема үшін Бульдік функциямен көрсетіледі; мысалы, кіріс биттері үшін схеманың шығыс биті математикалық түрде келесідей көрсетіледі. Схема Бульдік функцияны есептейді деп айтылады. Кез келген схеманың кіріс төбелерінің саны белгілі, сондықтан ол тек сол өлшемдегі кірістерге ғана қолданыла алады. Дегенмен, тілдер (шешімдік проблемалардың формальды ұсынылуы) әртүрлі ұзындықтағы тізбектерді қамтиды, сондықтан тілдерді бір ғана схема толыққанды қамти алмайды (бұл Тьюринг машинасының моделінен өзгеше, онда тілді кез келген кіріс өлшемімен жұмыс жасай алатын бір Тьюринг машинасы толық сипаттайды). Сондықтан тіл схемалар отбасымен көрсетіледі. Схемалар отбасы — бұл шексіз схемалар тізімі, мұнда — кіріс айнымалылары бар схема. Схемалар отбасы тілді шешеді деп айтылады, егер әрбір тізбек үшін , тілге жататын болса, ғана , мұнда — тізбектің ұзындығы. Басқаша айтқанда, өлшемі бар тізбек схемалар отбасымен көрсетілген тілге жатады, егер схема (кіріс төбелерінің саны тізбектегі биттер санымен тең схема) кіріс ретінде алғанда 1-ге тең нәтиже берсе. Тьюринг машиналарымен анықталған күрделілік кластары уақыт күрделілігі тұрғысынан сипатталса, схема күрделілігі кластары схеманың өлшемі — схемадағы төбелер саны тұрғысынан анықталады. Схемалар отбасының өлшемдік күрделілігі — функциясы, мұнда — схеманың өлшемі. Таныс функция кластары осыдан табиғи түрде туындайды; мысалы, полиномиалдық өлшемді схемалар отбасы — функцияның полиномиалдығын қамтамасыз ететін отбасы.

An alternative model of computation to the Turing machine is the Boolean circuit, a simplified model of the digital circuits used in modern computers. Not only does this model provide an intuitive connection between computation in theory and computation in practice, but it is also a natural model for non uniform computation (computation in which different input sizes within the same problem use different algorithms). Formally, a Boolean circuit is a directed acyclic graph in which edges represent wires (which carry the bit values 0 and 1), the input bits are represented by source vertices (vertices with no incoming edges), and all non source vertices represent logic gates (generally the AND, OR, and NOT gates). One logic gate is designated the output gate, and represents the end of the computation. The input/output behavior of a circuit with input variables is represented by the Boolean function ; for example, on input bits , the output bit of the circuit is represented mathematically as The circuit is said to compute the Boolean function
Any particular circuit has a fixed number of input vertices, so it can only act on inputs of that size. Languages (the formal representations of decision problems), however, contain strings of differing lengths, so languages cannot be fully captured by a single circuit (this contrasts with the Turing machine model, in which a language is fully described by a single Turing machine that can act on any input size). A language is thus represented by a circuit family. A circuit family is an infinite list of circuits , where is a circuit with input variables. A circuit family is said to decide a language if, for every string , is in the language if and only if , where is the length of In other words, a string of size is in the language represented by the circuit family if the circuit (the circuit with the same number of input vertices as the number of bits in ) evaluates to 1 when is its input. While complexity classes defined using Turing machines are described in terms of time complexity, circuit complexity classes are defined in terms of circuit size — the number of vertices in the circuit. The size complexity of a circuit family is the function , where is the circuit size of The familiar function classes follow naturally from this; for example, a polynomial size circuit family is one such that the function is a polynomial.

Күрделілік кластары

P/poly күрделілік класы – бұл полиномдық өлшемді схемалар отбасы арқылы шешілетін тілдер жиынтығы. Схема күрделілігі мен уақыт күрделілігі арасында табиғи байланыс бар екені анықталды. Интуитивті түрде, кішкентай уақыт күрделілігіне ие тіл (яғни, Тьюринг машинасынан салыстырмалы түрде аз тізбекті операциялар қажет), сонымен қатар кішкентай схема күрделілігіне ие болады (яғни, салыстырмалы түрде аз бульдік операциялар қажет). Формальды түрде, егер тіл , мұнда функциясы болса, онда оның схема күрделілігі бар екені көрсетілуі мүмкін. Бұл тікелей осы фактіден туындайды. Басқаша айтқанда, детерминистік Тьюринг машинасымен полиномдық уақытта шешілетін кез келген мәселені полиномдық өлшемді схемалар отбасымен де шешуге болады. Бұл кірістіру дұрыс, яғни (мысалы, P/poly-де шешілмейтін кейбір мәселелер бар). P/poly күрделілік кластары арасындағы қатынастарды зерттеуде өте пайдалы бірқатар қасиеттерге ие. Атап айтқанда, ол P және NP-ге қатысты мәселелерді зерттеуде көмектеседі. Мысалы, егер NP-де P/poly-де жоқ тіл болса, онда P/poly полиномдық иерархияның қасиеттерін зерттеуде де пайдалы. Мысалы, егер NP ⊆ P/poly болса, онда PH құлдырайды. P/poly және басқа күрделілік кластары арасындағы қатынастардың толық сипаттамасы "P/poly маңыздылығы" деген мақалада қолжетімді. P/poly Тьюринг машиналарының қасиеттерін жалпы зерттеуде де пайдалы, өйткені бұл класс полиномдық уақытпен жұмыс істейтін және полиномдық шектелген кеңес функциясына ие Тьюринг машинасымен танылатын тілдер класы ретінде эквивалентті түрде анықталуы мүмкін. P/poly-дің өзіндік қызықты қасиеттері бар екі субклассы – NC және AC. Бұл кластар схема өлшемі бойынша ғана емес, сонымен қатар тереңдігі бойынша да анықталады. Схеманың тереңдігі – кіріс түйінінен шығыс түйініне дейінгі ең ұзын бағытталған жолдың ұзындығы. NC класы – бұл полиномдық өлшемге және полилогарифмдік тереңдікке ие болумен шектелген схемалар отбасы арқылы шешілетін тілдер жиынтығы. AC класы NC-ге ұқсас анықталады, бірақ қақпаларға шексіз желдеткішке ие болуға рұқсат етіледі (яғни, AND және OR қақпалары екіден астам битке қолданылуы мүмкін). NC ерекше класс болып табылады, өйткені оны тиімді параллель алгоритмдері бар тілдер класы ретінде эквивалентті түрде анықтауға болады.

The complexity class P/poly is the set of languages that are decidable by polynomial size circuit families. It turns out that there is a natural connection between circuit complexity and time complexity. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in , where is a function , then it has circuit complexity It follows directly from this fact that In other words, any problem that can be solved in polynomial time by a deterministic Turing machine can also be solved by a polynomial size circuit family. It is further the case that the inclusion is proper, i. e. (for example, there are some undecidable problems that are in P/poly). P/poly has a number of properties that make it highly useful in the study of the relationships between complexity classes. In particular, it is helpful in investigating problems related to P versus NP. For example, if there is any language in NP that is not in P/poly, then P/poly is also helpful in investigating properties of the polynomial hierarchy. For example, if NP ⊆ P/poly, then PH collapses to A full description of the relations between P/poly and other complexity classes is available at "Importance of P/poly". P/poly is also helpful in the general study of the properties of Turing machines, as the class can be equivalently defined as the class of languages recognized by a polynomial time Turing machine with a polynomial bounded advice function. Two subclasses of P/poly that have interesting properties in their own right are NC and AC. These classes are defined not only in terms of their circuit size but also in terms of their depth. The depth of a circuit is the length of the longest directed path from an input node to the output node. The class NC is the set of languages that can be solved by circuit families that are restricted not only to having polynomial size but also to having polylogarithmic depth. The class AC is defined similarly to NC, however gates are allowed to have unbounded fan in (that is, the AND and OR gates can be applied to more than two bits). NC is a notable class because it can be equivalently defined as the class of languages that have efficient parallel algorithms.

Кванттық есептеулер

Кванттық ақпараттану ғылымында маңызды рөл атқаратын BQP және QMA кластары кванттық Тьюринг машиналарын қолдану арқылы анықталады.

Проблемалардың басқа түрлері

Компьютерлік ғалымдар зерттейтін күрделілік сыныптарының көп бөлігі шешім есептерінің жиынтығы болғанымен, басқа да түрдегі есептермен анықталатын күрделілік сыныптары да бар. Атап айтқанда, сану есептері, функциялық есептер және міндеттеме есептерінен тұратын күрделілік сыныптары бар. Бұл мәселелер төменде кеңірек түсіндіріледі.

Санау проблемалары

Санау мәселесі шешімнің бар-жоғын ғана емес (шешім мәселесі сияқты), сонымен қатар қанша шешім бар екенін сұрайды. Мысалы, шешім мәселесі белгілі бір графтың қарапайым циклы бар ма деп сұрайды (жауап қарапайым «иә»/«жоқ»); ал сәйкес келетін санау мәселесі («шарп цикл» деп аталады) қанша қарапайым цикл бар екенін сұрайды. Санау мәселесінің нәтижесі – сан, ал шешім мәселесінің нәтижесі – қарапайым «иә»/«жоқ» (немесе «қабылдау»/«разылықсыз», 0/1 немесе басқа да ұқсас схема). Осылайша, шешім мәселелері математикалық тұрғыдан формальды тілдер ретінде көрсетілсе, санау мәселелері математикалық тұрғыдан функциялар ретінде көрсетіледі: санау мәселесі функция ретінде формальдастырылады, яғни әрбір кіріс үшін , – шешімдер саны. Мысалы, мәселесінде кіріс – граф (биттер тізбегі түрінде көрсетілген граф), ал – графтың қарапайым циклдарының саны. Санау мәселелері статистикалық есептеу, статистикалық физика, желілік жобалау және экономика сияқты бірқатар салаларда туындайды.

Күрделілік кластары

#P (айтылуы "кескір P") – NP-нің санау түрі ретінде қарастырылатын есептеу мәселелерінің маңызды класы. NP-мен байланыс мәселенің шешімдерінің саны нон-детерминистік Тьюринг машинасының есептеу ағашындағы қабылданатын тармақтар санына тең болғандықтан туындайды. #P формальды түрде былай анықталады: #P – бұл барлық функциялар жиыны, яғни, полиномиалдық уақытта жұмыс істейтін нон-детерминистік Тьюринг машинасы бар, және барлық үшін , функциясының есептеу ағашындағы қабылданатын тармақтар санына тең болады.

Ал NP-ні детерминизм және тексеруші тұрғысынан (яғни, интерактивті дәлелдеу жүйесі ретінде) анықтауға болатындай, #P-ні де тексеруші тұрғысынан эквивалентті түрде анықтауға болады. Еске сала кетейік, шешімдік мәселе NP класында болады, егер берілген мәселе мысалына полиномиалдық уақытта тексерілетін сертификат болса – яғни, NP кірістік деректер үшін мүшелік дәлелінің (сертификатының) бар-жоқтығын сұрайды, оның дұрыстығын полиномиалдық уақытта тексеруге болады. #P класы осындай сертификаттардың қаншасы бар екенін сұрайды. Осы контексте #P былай анықталады: #P – бұл функциялар жиыны, яғни полиномиал және полиномиалдық уақытта жұмыс істейтін Тьюринг машинасы (тексеруші) бар, сонда әрбір үшін , функциясының полиномиалдық өлшемдегі барлық сертификаттарын қамтитын жиынның өлшеміне тең болады.

Функционалдық мәселелер

Санау проблемалары функциялық проблемалар деп аталатын кеңірек проблемалар класының ішкі жиыны болып табылады. Функциялық проблема – бұл функцияның мәндері есептелетін проблема түрі. Формальды түрде, функциялық проблема кез келген әліпби тізбектері бойынша қатынас ретінде анықталады:

Алгоритм егер әрбір кіріс үшін , оны қанағаттандыратын бар болса, алгоритм осындай мәнді шығарады деп шешеді. Бұл функция екенін және алгоритм оны барлық үшін шешеді дегеннің тағы бір жолы.

Күрделілік кластары

Функцияның күрделілік класы FP, тиімді шешілетін функциялар класы болып табылады. Нақтырақ айтқанда, FP – бұл детерминистік Тьюринг машинасы полиномиалдық уақытта шеше алатын функциялық есептер жиынтығы. FP-ны P класының функциялық есептерге арналған баламасы деп қарастыруға болады. FP есептеу проблемаларына, сондай-ақ P және NP арақатынасына түсінік береді. Егер #P=FP болса, онда NP класындағы есептер үшін куәліктер санын анықтайтын функциялар тиімді шешіледі. Куәліктер санын есептеу, куәліктің бар-жоғын анықтаудан кем емес қиындыққа толы болғандықтан, #P=FP болса, онда P=NP болуы керек (бірақ керісінше дұрыс па, яғни P=NP #P=FP дегенді білдіреді ме, белгісіз). FP, P класының функциялық есептерге арналған баламасы болса, FNP, NP класының функциялық есептерге арналған баламасы болып табылады. FP=FNP тек қана P=NP болған жағдайда ғана орын алады.