Есептеу қиындықтарының теориясы

Есептеу қиындықтары: Компьютерлік проблемалардың ресурстық талаптарын, алгоритмдерді және математикалық модельдерді зерттейтін теория.

20 мин оқу

100%

Дереккөз: Computational complexity theory — Wikipedia

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

Мазмұны

Кіріспе

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

Inherent difficulty of computational problems

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i. e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is part of the field of computational complexity. Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.

Проблемалық жағдайлар

Есептеулік мәселені әрбір жағдай үшін шешімдер жиынтығы (мүмкін бос) бар, шексіз инстанстар жиынтығы ретінде қарастыруға болады. Есептеулік мәселенің кіріс тізбегі мәселенің инстанциясы деп аталады және оны мәселенің өзімен шатастыруға болмайды. Есептеу күрделілігі теориясында мәселе – шешілетін абстракт сұрақ. Керісінше, бұл мәселенің инстанциясы – шешімдік мәселенің кірісі ретінде қолданылатын нақтылы мәлімдеме. Мысалы, жай сан тексеру мәселесін қарастырайық. Инстанция – сан (мысалы, 15), ал егер сан жай болса, шешімі «иә», әйтпесе «жоқ» (бұл жағдайда 15 жай сан емес, жауап «жоқ»). Басқаша айтқанда, инстанция – мәселенің нақты кірісі, ал шешім – берілген кіріске сәйкес келетін шығыс. Мәселе мен инстанция арасындағы айырмашылықты одан да анық көрсету үшін, саяхатшы сатушы мәселесінің шешімдік нұсқасының келесі инстанциясын қарастырайық: Германияның ең ірі 15 қаласының барлығынан өтетін, ең көп дегенде 2000 километрлік маршрут бар ма? Бұл нақты мәселенің сандық жауабы мәселенің басқа инстанцияларын шешу үшін көбінесе пайдалы емес, мысалы, Милан қаласындағы барлық нысандарды аралап, жалпы ұзындығы 10 км-ден аспайтын саяхат туралы сұрау. Сондықтан күрделілік теориясы нақты мәселе инстанцияларын емес, есептеулік мәселелерді зерттейді.

Проблемалық инстанстарды көрсету

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

Ресми тілдер ретінде шешімдер қабылдау проблемалары

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

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

Функциялық есеп – әрбір кіріс үшін жалпы функцияның бір ғана шығысы күтілетін есеп, бірақ шығысы шешім есебінен күрделірек, яғни шығыс тек "иә" немесе "жоқ" бола бермейді. Көрінетін мысалдарға саяхатшы сатушысының есебі және бүтін сандарды көбейткіштерге жіктеу есебі жатады. Функциялық есептер ұғымы шешім есептерінен әлдеқайда толық деп ойлауға болады. Дегенмен, бұл іс жүзінде солай емес, себебі функциялық есептерді шешім есептері түрінде қарастыруға болады. Мысалы, екі бүтін санның көбейтілуі a × b = c қатынасын қанағаттандыратын (a, b, c) үштіктері жиыны ретінде беріледі. Берілген үштіктің осы жиынға жата ма, жатпай ма, деген сұраққа жауап беру екі санды көбейту есебін шешумен тең.

Үлгі өлшемін өлшеу

Есептеулік мәселені шешудің қиындығын өлшеу үшін, ең жақсы алгоритмнің мәселені шешуге қажетті уақытын қарастыруға болады. Дегенмен, алгоритмнің жұмыс істеу уақыты, әдетте, мәселенің нақты түріне байланысты өзгеруі мүмкін. Атап айтқанда, үлкен мәселелерді шешуге көбірек уақыт керек болады. Сондықтан, мәселені шешуге қажетті уақыт (немесе қажетті жад, немесе күрделіліктің кез келген өлшемі) мәселенің мөлшерінің функциясы ретінде есептеледі. Бұл көбінесе кіріс деректерінің битке шаққандағы мөлшері ретінде қарастырылады. Күрделілік теориясы алгоритмдердің кіріс мөлшерінің өсуімен қалай өзгеретінін зерттейді. Мысалы, графтың байланысты екенін анықтау мәселесінде, 2n төбесі бар графты шешуге, n төбесі бар графты шешуге қарағанда қанша уақыт артық керек болады? Егер кіріс мөлшері n болса, онда уақыт n функциясы арқылы өрнектеледі. Бірдей мөлшердегі әртүрлі кіріс деректері үшін жұмсалатын уақыт әртүрлі болуы мүмкін болғандықтан, ең нашар жағдайдағы уақыт күрделілігі T(n) – n мөлшеріндегі барлық кіріс деректері үшін жұмсалатын ең көп уақыт ретінде анықталады. Егер T(n) n-ге қатысты полином болса, онда алгоритм полиномиалдық уақыт алгоритмі деп аталады. Кобхамның тезисінде, егер мәселенің полиномиалдық уақыт алгоритмі болса, онда оны шешуге жеткілікті ресурстар бар екендігі айтылады.

Тьюринг машинасы

Тьюринг машинасы – жалпы есептеу машинасының математикалық моделі. Ол – таспадағы символдарды өңдейтін теориялық құрылғы. Тьюринг машиналары практикалық есептеу технологиясы ретінде емес, керісінше, озық суперкомпьютерден бастап қарындаш пен қағазбен жұмыс істейтін математикке дейінгі кез келген есептеу машинасының жалпы моделі ретінде қарастырылады. Егер бір мәселені алгоритм арқылы шешуге болады десе, онда сол мәселені шешетін Тьюринг машинасы бар деп саналады. Шындығында, бұл – Чёрч-Тьюринг тезисі. Сонымен қатар, бүгін бізге белгілі басқа есептеу модельдерінде, мысалы, RAM машинасы, Конвейдің «Өмір» ойыны, жасушалық автоматтар, лямбда-есептеу немесе кез келген бағдарламалау тілінде есептелетіннің бәрі Тьюринг машинасы арқылы есептелуі мүмкін. Тьюринг машиналарын математикалық тұрғыдан талдау оңай, және олар кез келген басқа есептеу моделімен шамалас қуатты деп есептеледі, сондықтан Тьюринг машинасы күрделілік теориясында ең көп қолданылатын модель болып табылады. Күрделілік кластарын анықтау үшін түрлі типтегі Тьюринг машиналары қолданылады, мысалы, детерминистік Тьюринг машиналары, ықтималдық Тьюринг машиналары, детерминистік емес Тьюринг машиналары, кванттық Тьюринг машиналары, симметриялық Тьюринг машиналары және алмасу Тьюринг машиналары. Бәрі де принцип бойынша бірдей қуатты, бірақ ресурстар (мысалы, уақыт немесе жад) шектелген жағдайда, олардың кейбіреулері басқаларынан артық күшке ие болуы мүмкін. Детерминистік Тьюринг машинасы – болашақ әрекеттерін анықтау үшін ережелердің белгілі бір жиынтығын пайдаланатын ең қарапайым Тьюринг машинасы. Ықтималдық Тьюринг машинасы – кездейсоқ биттердің қосымша көзін пайдаланатын детерминистік Тьюринг машинасы. Ықтималдық шешімдер қабылдау мүмкіндігі алгоритмдерге мәселелерді тиімдірек шешуге көмектеседі. Кездейсоқ биттерді пайдаланатын алгоритмдер кездейсоқ алгоритмдер деп аталады. Детерминистік емес Тьюринг машинасы – детерминистік емес мүмкіндігі бар детерминистік Тьюринг машинасы, ол Тьюринг машинасына белгілі бір күйде бірнеше болашақ әрекеттерді орындауға мүмкіндік береді. Детерминизмді қарастырудың бір жолы – Тьюринг машинасы әр қадамда көптеген мүмкін есептеу жолдарына бөлінеді, және егер ол осы жолдардың кез келгенінде мәселені шешсе, онда ол мәселені шешкен болып саналады. Бұл модель физикалық тұрғыдан іске асырылатын модель емес, ол тек теориялық тұрғыдан қызықты абстрактілі машина, ол ерекше қызықты күрделілік кластарын тудырады. Мысалдар үшін детерминистік емес алгоритмді қараңыз.

A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata, lambda calculus or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory. Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others. A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non deterministic Turing machine is a deterministic Turing machine with an added feature of non determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non deterministic algorithm.

Басқа машина үлгілері

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

Күрделілік шаралары

Белгілі бір уақыт пен кеңістікті пайдаланып мәселені шешудің не екенін нақты анықтау үшін, детерминистік Тьюринг машинасы сияқты есептеу моделі қолданылады. Детерминистік Тьюринг машинасы M кіріс x-ке қажетті уақыт – машина тоқтап, жауап ("иә" немесе "жоқ") шығару алдында жасайтын күйлердің немесе қадамдардың жалпы саны. Егер M машинасының әр n ұзындығындағы кіріске қажетті уақыты f(n) болса, онда M Тьюринг машинасы f(n) уақытында жұмыс істейді. Шешімдік мәселе A, егер f(n) уақытында жұмыс істейтін және осы мәселені шешетін Тьюринг машинасы болса, f(n) уақытында шешіледі. Күрделілік теориясы проблемаларды олардың қиындығына қарай жіктеуге бағытталғандықтан, белгілі бір критерийлерге негізделген проблемалар жиынын анықтайды. Мысалы, детерминистік Тьюринг машинасының f(n) уақытында шешілетін проблемалар жиыны DTIME(f(n)) деп белгіленеді. Кеңістік талаптарына да ұқсас анықтамалар жасауға болады. Уақыт пен кеңістік ең танымал күрделілік ресурстары болғанымен, кез келген күрделілік өлшемін есептеу ресурсы ретінде қарастыруға болады. Күрделілік өлшемдері Блумның күрделілік аксиомаларымен жалпы түрде анықталады. Күрделілік теориясында қолданылатын басқа күрделілік өлшемдері: коммуникациялық күрделілік, схемалық күрделілік және шешім ағашының күрделілігі. Алгоритмнің күрделілігі көбінесе үлкен O нотациясы арқылы көрсетіледі.

Ең жақсы, ең нашар және орташа күрделілік

Ең жақсы, ең нашар және орташа жағдай күрделілігі – бірдей өлшемдегі әртүрлі кірістердің уақыт күрделілігін (немесе кез келген басқа күрделілік өлшемін) бағалаудың үш әртүрлі тәсілі. Кейбір n өлшемді кірістерді шешу басқаларына қарағанда жылдам болуы мүмкін болғандықтан, келесі күрделіліктерді анықтаймыз: Ең жақсы жағдай күрделілігі: Бұл n өлшемді ең жақсы кіріс үшін мәселені шешу күрделілігі. Орташа жағдай күрделілігі: Бұл мәселені орташа есеппен шешу күрделілігі. Бұл күрделілік тек кірістердің ықтималдық таралымына қатысты анықталады. Мысалы, егер бірдей өлшемдегі барлық кірістердің пайда болу мүмкіндігі бірдей болса, орташа жағдай күрделілігі n өлшемді барлық кірістер бойынша біркелкі таралымға қатысты анықталуы мүмкін. Амортизацияланған талдау: Амортизацияланған талдау алгоритмнің барлық операциялар тізбегі бойынша қымбат және аз қымбат операцияларды бірге қарастырады. Ең нашар жағдай күрделілігі: Бұл n өлшемді ең нашар кіріс үшін мәселені шешу күрделілігі. Арзаннан қымбатқа дейінгі рет: Ең жақсы, орташа (дискретті біркелкі таралымның), амортизацияланған, ең нашар. Мысалы, детерминистік сұрыптау алгоритмі quicksort-ты қарастырайық. Бұл кіріс ретінде берілген бүтін сандар тізімін сұрыптау мәселесін шешеді. Ең нашар жағдай – pivot әрқашан тізімдегі ең үлкен немесе ең кіші мән болғанда (сол себепті тізім ешқашан бөлінбейді). Бұл жағдайда алгоритм O(n²) уақыт алады. Егер кіріс тізімінің барлық мүмкін орналасуларының пайда болу мүмкіндігі бірдей деп есептесек, сұрыптау үшін жұмсалатын орташа уақыт O(n log n) болады. Ең жақсы жағдай әрбір pivot тізімді екіге бөлетін кезде пайда болады, бұл да O(n log n) уақытты қажет етеді.

Мәселелердің күрделілігінің жоғарғы және төменгі шектері

Есептеу уақытын (немесе жадты пайдалану сияқты басқа да ресурстарды) жіктеу үшін, берілген мәселені шешуге ең тиімді алгоритмге қажетті ең көп уақыттың жоғарғы және төменгі шектерін көрсету пайдалы. Егер басқаша көрсетілмесе, алгоритмнің күрделілігі оның ең нашар жағдайдағы күрделілігі деп есептеледі. Нақты алгоритмді талдау – алгоритмдерді талдау саласына жатады. Мәселенің уақыт күрделілігі үшін T(n) жоғарғы шегін көрсету үшін, орындалу уақыты T(n) шамасында болатын нақты алгоритмнің бар екенін көрсету жеткілікті. Дегенмен, төменгі шектерді дәлелдеу әлдеқайда қиын, себебі төменгі шектер берілген мәселені шешетін барлық мүмкін алгоритмдер туралы мәлімдеме жасайды. "Барлық мүмкін алгоритмдер" деген сөз тіркесі бүгінгі күні белгілі алгоритмдерді ғана емес, болашақта ашылуы мүмкін кез келген алгоритмді де қамтиды. Мәселе үшін T(n) төменгі шегін көрсету үшін, ешқандай алгоритмнің уақыт күрделілігі T(n) шегінен төмен болмайтынын көрсету қажет. Жоғарғы және төменгі шектер әдетте үлкен О белгісін пайдалану арқылы көрсетіледі, ол тұрақты коэффициенттер мен кіші мүшелерді жасырады. Бұл шектерді қолданылған есептеу моделінің нақты ерекшеліктеріне тәуелсіз етеді. Мысалы, егер T(n) = 7n² + 15n + 40 болса, үлкен О белгісімен T(n) = O(n²) деп жазылады.

Күрделілік сыныптарын анықтау

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

Детерминистік Тьюринг машинасы арқылы f(n) уақытында шешілетін шешім проблемаларының жиынтығы. (Бұл күрделілік класы DTIME(f(n)) деп аталады.) Бірақ есептеу уақытын қандай да бір нақты функция f(n) арқылы шектеу көбінесе таңдалған машина моделіне байланысты күрделілік кластарын тудырады. Мысалы, {xx | x – кез келген екілік тізбек} тілін көп таспалы Тьюринг машинасымен сызықтық уақытта шешуге болады, бірақ бір таспалы Тьюринг машиналарының моделінде міндетті түрде квадраттық уақыт қажет. Егер біз орындалу уақытында полиномиалдық өзгерістерге рұқсат берсек, Кобхэм-Эдмондс тезисі «компьютерлік есептеудің кез келген екі ақылға қонымды және жалпы модельдеріндегі уақыт күрделілігі полиномиалдық байланысты» дейді. Бұл күрделілік класы P үшін негіз болып табылады, ол детерминистік Тьюринг машинасымен шешілетін шешім проблемаларының жиынтығы. Функциялық проблемалардың сәйкес жиынтығы FP болып табылады.

Кішірейту

Көптеген күрделілік кластары редукция түсінігі арқылы анықталады. Редукция – бұл бір мәселенің екінші мәселеге түрлендірілуі. Ол бір мәселенің екіншісінен көп қиын емес екендігі туралы бейресми ұғымды қамтиды. Мысалы, егер X мәселесі Y алгоритмін қолдану арқылы шешілсе, X мәселесі Y-дан қиын емес, және X мәселесі Y-ге дейін редукцияланады дейміз. Редукциялау әдісіне байланысты түрлі редукциялар бар, мысалы, Кук редукциялары, Карп редукциялары және Левин редукциялары, сондай-ақ редукциялардың күрделілігіне байланысты, мысалы, полиномиалдық уақыт редукциялары немесе логарифмдік кеңістік редукциялары. Ең көп қолданылатын редукция – полиномиалдық уақыт редукциясы. Бұл редукциялау процесі полиномиалдық уақытты қажет етеді дегенді білдіреді. Мысалы, бүтін санды квадраттау мәселесі екі бүтін санды көбейту мәселесіне дейін редукцияланады. Яғни, екі бүтін санды көбейту алгоритмі бүтін санды квадраттау үшін қолданылуы мүмкін. Бұл көбейту алгоритмінің екі кірісіне де бірдей мәнді беру арқылы орындалуы мүмкін. Осылайша, квадраттау көбейтуден қиын емес екенін көреміз, себебі квадраттау көбейтуге дейін редукцияланады. Бұл күрделілік класы үшін қиын мәселе түсінігін қалыптастырады. Егер C класындағы кез келген мәселені X-ке дейін редукциялау мүмкін болса, X мәселесі C класы үшін қиын мәселе болып саналады. Сондықтан C класындағы ешқандай мәселе X-тен қиын емес, өйткені X-ке арналған алгоритм C класындағы кез келген мәселені шешуге мүмкіндік береді. Қиын мәселелер туралы ұғым қолданылатын редукция түріне байланысты. P класынан үлкен күрделілік кластары үшін полиномиалдық уақыт редукциялары жиі қолданылады. Атап айтқанда, NP үшін қиын мәселелер жиыны – NP-қиын мәселелер жиыны. Егер X мәселесі C класында болса және C класы үшін қиын болса, онда X мәселесі C класына толық деп айтылады. Бұл X мәселесі C класындағы ең қиын мәселе дегенді білдіреді (көптеген мәселелер бірдей қиын болуы мүмкін болғандықтан, X мәселесі C класындағы ең қиын мәселелердің бірі деп айтуға болады). Осылайша, NP-толық мәселелер класы NP класындағы ең қиын мәселелерді қамтиды, себебі олар P класына жатпауы мүмкін. P = NP мәселесі шешілмегендіктен, белгілі NP-толық мәселені, Π2, басқа мәселеге, Π1, редукциялауға мүмкіндік беру, Π1 мәселесі үшін белгілі полиномиалдық уақыт шешімі жоқ екенін көрсетеді. Өйткені Π1 мәселесіне полиномиалдық уақыт шешімі табылуы Π2 мәселесіне полиномиалдық уақыт шешімін табуға мүмкіндік береді. Сол сияқты, барлық NP мәселелерін бір жиынға редукциялауға болатындықтан, полиномиалдық уақытта шешілетін NP-толық мәселені табу P = NP екенін білдіреді.

Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial time reductions or log space reductions. The most commonly used reduction is a polynomial time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication. This motivates the concept of a problem being hard for a complexity class. A problem X is hard for a class of problems C if every problem in C can be reduced to X. Thus no problem in C is harder than X, since an algorithm for X allows us to solve any problem in C. The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP hard problems. If a problem X is in C and hard for C, then X is said to be complete for C. This means that X is the hardest problem in C. (Since many problems could be equally hard, one might say that X is one of the hardest problems in C.) Thus the class of NP complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP complete problem, Π2, to another problem, Π1, would indicate that there is no known polynomial time solution for Π1. This is because a polynomial time solution to Π1 would yield a polynomial time solution to Π2. Similarly, because all NP problems can be reduced to the set, finding an NP complete problem that can be solved in polynomial time would mean that P = NP.]]

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

P күрделілік класы көбінесе тиімді алгоритмге ие есептеу міндеттерін модельдейтін математикалық абстракция ретінде қарастырылады. Бұл гипотеза Кобхам-Эдмондс тезисі деп аталады. NP күрделілік класы, керісінше, адамдар тиімді шешуді қалайтын, бірақ тиімді алгоритмі белгілі емес көптеген проблемаларды қамтиды, мысалы, Бульдік қанағаттандыру мәселесі, Гамильтондық жол мәселесі және төбелік жабу мәселесі. Детерминистік Тьюринг машиналары детерминистік емес Тьюринг машиналарының ерекше жағдайы болғандықтан, P класындағы әрбір мәселенің NP класының да мүшесі екені оңай көрінеді. P тең NP ме деген сұрақ теориялық информатикадағы ең маңызды ашық сұрақтардың бірі болып табылады, өйткені оның шешімі кең ауқымды салдарға ие. Егер жауап "иә" болса, көптеген маңызды проблемаларға тиімдірек шешімдер табылуы мүмкін. Оларға операциялық зерттеудегі түрлі типтегі бүтін сандық бағдарламалау мәселелері, логистикадағы көптеген мәселелер, биологиядағы белок құрылымын болжау және таза математика теоремаларының формальды дәлелдемелерін табу қабілеті кіреді. P және NP мәселесі – Клей математика институты ұсынған Мыңжылдық сыйлықтарының бірі. Бұл мәселені шешуге 1 000 000 АҚШ доллары сыйлық белгіленген.

NP-дегі P немесе NP-толық деп танылмаған проблемалар

Ладнер көрсеткендей, егер P ≠ NP болса, онда NP-де P-ге де, NP-толық емес мәселелер бар. Егер граф изоморфизмі NP-толық болса, полиномиалдық уақыт иерархиясы екінші деңгейге дейін құлайды. Полиномиалдық иерархияның кез келген шекті деңгейге құламайтынына кеңінен сенеді, сондықтан граф изоморфизмі NP-толық емес деп есептеледі. Бұл мәселені шешудің ең жақсы алгоритмі Ласло Бабаи мен Юджин Люкс еңбегімен жасалған, n төбесі бар графтар үшін оның орындалу уақыты болды, бірақ Бабаидің соңғы жұмыстары осы мәселеге қатысты жаңа көзқарастар ұсынады. Бүтін санды факторлау мәселесі – берілген бүтін санның жай көбейткіштерін анықтаудың есептеулік мәселесі. Шешім ретінде қойылғанда, бұл мәселе кіріс k-дан кіші жай көбейткішке ие ме, жоқ па, дегенді анықтаудан тұрады. Тиімді бүтін санды факторлау алгоритмі белгілі емес, және осы фактінің негізінде RSA алгоритмі сияқты бірнеше қазіргі заманғы криптографиялық жүйелер құрылған. Бүтін санды факторлау мәселесі NP және co NP-де (сондай-ақ UP және co UP-де) орналасқан. Егер мәселе NP-толық болса, полиномиалдық уақыт иерархиясы бірінші деңгейге дейін құлайды (яғни NP, co NP-ге тең болады). Бүтін санды факторлаудың ең белгілі алгоритмі – жалпы сандық өріс елегі, ол жұп емес бүтін санды n-ді факторлауға уақыт алады. Дегенмен, бұл мәселеге арналған ең белгілі кванттық алгоритм – Шор алгоритмі, ол полиномиалдық уақытта жұмыс істейді. Алайда, бұл факт кванттық емес күрделілік кластарына қатысты мәселенің орналасуы туралы көп мәлімет бермейді.

Басқа күрделілік сыныптары арасындағы бөліну

Көптеген белгілі күрделілік сыныптары тең емес деп күдіктенеді, бірақ бұл дәлелденбеді. Мысалы, P ⊆ NP ⊆ PP ⊆ PSPACE, бірақ P = PSPACE болуы мүмкін. Егер P, NP-ге тең болмаса, онда P, PSPACE-ке де тең болмайды. P және PSPACE арасында RP, BPP, PP, BQP, MA, PH сияқты көптеген белгілі күрделілік сыныптары бар болғандықтан, осы күрделілік сыныптарының барлығы бір сыныпқа бірігуі мүмкін. Осы сыныптардың кез келгенінің тең емес екенін дәлелдеу күрделілік теориясында маңызды жаңалық болар еді. Сол сияқты, co NP – NP проблемаларының толықтыру проблемаларын (яғни, жауабы «иә/жоқ» кері аударылған проблемалар) қамтитын сынып. NP, co NP-ге тең емес деп есептеледі, бірақ бұл әлі дәлелденбеді. Егер осы екі күрделілік сыныбы тең болмаса, онда P, NP-ге тең емес, себебі P = co P. Осылайша, егер P = NP болса, онда co P = co NP болады, демек NP = P = co P = co NP. Сол сияқты, L (логарифмдік кеңістікте шешілетін барлық проблемалардың жиынтығы) P-нің ішіне қатаң түрде кіре ме, әлде P-ге тең ме, бұл белгісіз. Тағы да, екеуінің арасында NL және NC сияқты көптеген күрделілік сыныптары бар, және олардың бөлек немесе тең сыныптар екені белгісіз. P және BPP тең деп күдіктенеді. Алайда, BPP = NEXP болатыны қазіргі таңдағы ашық мәселе.

Тартылу мүмкіндігі

Теориялық тұрғыдан шешілуі мүмкін (мысалы, үлкен, бірақ шекті ресурстар, әсіресе уақыт берілгенде), бірақ іс жүзінде кез келген шешім пайдалы болу үшін тым көп ресурстарды қажет ететін мәселе, шешілмейтін мәселе деп аталады. Керісінше, тәжірибеде шешілетін мәселе "қолдануға болатын мәселе" деп аталады. "Орындалмайтын" (сөзбе-сөз "істеуге болмайды") термині кейде шешілмейтінмен алмастырылып қолданылады, бірақ бұл математикалық оптимизациядағы мүмкін шешіммен шатастыруға әкелуі мүмкін. Шешілетін мәселелер жиі полиномиалдық уақытта шешілетін мәселелермен (P, PTIME) анықталады; бұл Кобхам-Эдмондс тезисі деп аталады. Осы мағынада шешілмейтін деп танылған мәселелерге EXPTIME қиындықтары жатады. Егер NP, P-мен бірдей болмаса, онда NP қиын мәселелер де осы мағынада шешілмейтін болады. Дегенмен, бұл сәйкестік толық емес: үлкен дәрежелі немесе үлкен жетекші коэффициенті бар полиномиалдық уақыт шешімі тез өседі және практикалық өлшемдегі мәселелер үшін тиімді болмауы мүмкін; керісінше, баяу өсетін экспоненциалдық уақыт шешімі нақты деректермен практикалық болуы мүмкін, немесе ең жаман жағдайда ұзақ уақыт алатын шешім, көп жағдайда немесе орташа жағдайда қысқа уақыт алуы мүмкін, сондықтан да практикалық болуы мүмкін. Мәселе P-ге жатпайды деу, мәселенің барлық үлкен жағдайлары қиын немесе тіпті олардың көпшілігі қиын дегенді білдірмейді. Мысалы, Пресбургер арифметикасындағы шешім мәселесі P-ге жатпайтыны көрсетілді, бірақ көптеген жағдайларда мәселені ақылға қонымды уақытта шешетін алгоритмдер жазылды. Сол сияқты, алгоритмдер NP-толық рюкзак мәселесін квадраттық уақыттан кем уақытта кең ауқымда шеше алады және SAT шешушілер NP-толық Бульдық қанағаттандыру мәселесінің үлкен мысалдарымен жүйелі түрде айналысады. Экспоненциалдық уақыт алгоритмдерінің іс жүзінде неге қолданылмайтынын түсіну үшін тоқтау алдында 2n операция жасайтын бағдарламаны қарастырайық. Кішкентай n үшін, мысалы, 100 және компьютер әр секундта 1012 операция жасайды деп есептесек, бағдарлама шамамен 4 × 1010 жыл бойы жұмыс істейді, бұл ғаламның жасымен шамамен бірдей. Тіпті әлдеқайда жылдам компьютерде де бағдарлама өте аз мысалдар үшін ғана пайдалы болады және осы тұрғыдан алғанда мәселенің шешілмейтіндігі технологиялық прогреске байланысты емес. Дегенмен, 1.0001n операцияны қабылдайтын экспоненциалдық уақыт алгоритмі n салыстырмалы түрде үлкен болғанша практикалық болып табылады. Сол сияқты, полиномиалдық уақыт алгоритмі әрқашан да практикалық емес. Егер оның жұмыс істеу уақыты, мысалы, n15 болса, оны тиімді деп санаудың қажеті жоқ және ол кішкентай мысалдардан басқа жағдайларда да пайдасыз. Шындығында, іс жүзінде тіпті n3 немесе n2 алгоритмдері мәселелердің нақты өлшемдері бойынша жиі практикалық емес.

A problem that can be solved in theory (e. g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful, is known as an intractable problem. Conversely, a problem that can be solved in practice is called a tractable problem, literally "a problem that can be handled". The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable, though this risks confusion with a feasible solution in mathematical optimization. Tractable problems are frequently identified with problems that have polynomial time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME hard. If NP is not the same as P, then NP hard problems are also intractable in this sense. However, this identification is inexact: a polynomial time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP complete Boolean satisfiability problem. To see why exponential time algorithms are generally unusable in practice, consider a program that makes 2n operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 1012 operations each second, the program would run for about 4 × 1010 years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential time algorithm that takes 1.0001n operations is practical until n gets relatively large. Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n15, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n3 or n2 algorithms are often impractical on realistic sizes of problems.

Тұрақты күрделілік теориясы

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

Тарих

Алгоритмдік күрделілікті талдаудың алғашқы мысалы – 1844 жылы Габриэль Ламе жасаған Евклид алгоритмінің орындалу уақытын талдау. Алгоритмдік проблемалардың күрделілігіне арналған нақты зерттеулер басталғанға дейін әртүрлі зерттеушілер көптеген негіздер қалады. Олардың ең ықпалдысы – 1936 жылы Алан Тьюрингтің Тьюринг машиналарын анықтауы, ол компьютердің өте берік және икемді үлгісіне айналды. Есептеу күрделілігіндегі жүйелі зерттеулердің басталуы Юрис Хартманис пен Ричард Э. Стернстің 1965 жылғы «Алгоритмдердің есептеу күрделілігі туралы» мақаласына байланысты. Бұл мақалада уақыт және кеңістік күрделілігінің анықтамалары берілді және иерархия теоремалары дәлелденді. Сонымен қатар, 1965 жылы Эдмондс «жақсы» алгоритмнің орындалу уақыты кіріс мөлшерінің полиномымен шектелгені жөн деп ұсынды. Алдыңғы жұмыстарда нақты шектелген ресурстармен Тьюринг машиналары арқылы шешілетін мәселелерді зерттеуге арналған нақты уақыт есептеулері (1962) қарастырылды. Одан бұрын, КСРО-дан Борис Трахтенброт (1956) басқа бір күрделілік өлшемін зерттеді. Ол еске түсіргендей:

Дегенмен, [автоматтар теориясына] бастапқы қызығушылығым есептеу күрделілігіне, коммутациялық теориядан мұра етілген комбинаторлық әдістердің және алгоритмдер теориясының тұжырымдамалық құралдарының қызықты бірігіміне көшті. Бұл идеялар 1955 жылы мен «сигналдау функциясы» терминін қолданған кезде туды, ол қазір «күрделілік өлшемі» деп белгілі. 1967 жылы Мануэль Блум аксиомалар жиынтығын (қазір Блум аксиомалары деп аталады) құрастырды, ол есептеу функциялары жиынтығында күрделілік өлшемдерінің қажетті қасиеттерін көрсетеді және маңызды нәтиже – жылдамдық теоремасын дәлелдеді. Бұл сала 1971 жылы Стивен Кук пен Леонид Левин NP-толық болатын маңызды проблемалардың бар екенін дәлелдеген кезде дами бастады. 1972 жылы Ричард Карп бұл идеяны «Комбинаторлық проблемалар арасындағы кему» атты мақаласымен одан әрі дамытты, онда ол 21 әртүрлі комбинаторлық және граф теориялық проблемалардың, олардың әрқайсысы есептеу қиындығымен белгілі, NP-толық екенін көрсетті.