Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Есептеу күрделілігі теориясында шешім проблемасының толықтығы – бұл «иә» және «жоқ» жауаптарын ауыстыру арқылы алынатын шешім проблемасы. Балама ретінде, егер шешім проблемаларын шекті жолдар жиыны ретінде қарастырсақ, онда осы жиынның белгілі бір домендегі толықтығы – оның толықтыру проблемасы болады. Мысалы, маңызды проблеманың бірі – санның жай сан екендігін анықтау. Оның толықтығы – санның жай емес (құрама) сан екенін анықтау. Мұнда толықтыру домені – бірден үлкен барлық бүтін сандар жиыны. Кез келген проблеманың толықтыру проблемасына Тьюринг азайтуы бар. Толықтыру операциясы инволюция болып табылады, яғни ол «өзін жояды», немесе толықтырудың толықтығы бастапқы проблемаға тең. Бұл күрделілік класының толықтығына жалпыланады, ол кластағы әрбір проблеманың толықтығынан тұратын толықтыру класы деп аталады. Егер класс C деп белгіленсе, оның толықтығы әдетте co C деп белгіленеді. Ескеріңіз, бұл проблемалар жиыны ретінде күрделілік класының толықтығы емес, онда көптеген проблемалар болар еді. Класс толықтыру бойынша жабық деп есептеледі, егер классдағы кез келген проблеманың толықтығы да сол класқа жатса. Кез келген проблеманың толықтыруына Тьюринг азайтулары болғандықтан, Тьюринг азайтулары бойынша жабық кез келген класс толықтыру бойынша жабық болады. Толықтыру бойынша жабық класс өзінің толықтыру класына тең. Дегенмен, көптеген бірлік азайтулар бойынша, NP сияқты маңызды класс өзінің толықтыру класынан өзгеше деп есептеледі (бірақ бұл дәлелденбеген). Кез келген күрделілік класының Тьюринг азайтуы бойынша жабылуы – бұл класс толықтыру бойынша жабық болатын класстың үстін жиыны. Толықтыру бойынша жабылу – ең кіші мұндай класс. Класс өзінің толықтығымен қиылысса, толықтыру бойынша жабық (бос болуы мүмкін) ішкі жиынды аламыз. DSPACE(f(n)) және DTIME(f(n)) сияқты әрбір детерминистік күрделілік класы толықтыру бойынша жабық, өйткені алгоритмге жауапты ауыстыратын соңғы қадамды қосуға болады. Бұл нұсқаусыз күрделілік классдары үшін жұмыс істемейді, себебі егер қабылдау және қабылдамау жолдары болса, және барлық жолдар жауабын ауыстырса, қабылдау және қабылдамау жолдары қалады – нәтижесінде машина екі жағдайда да қабылдайды. Сол сияқты, BPP, ZPP, BQP немесе PP сияқты «иә» және «жоқ» мысалдарына қатысты симметриялық анықталған ықтималдық классдары толықтыру бойынша жабық. Керісінше, RP және co RP сияқты классдар олардың ықтималдықтарын бір жақты қатемен анықтайды, сондықтан олар (қазіргі уақытта белгілі) толықтыру бойынша жабық емес. Бүгінгі күнге дейін көрсетілген күрделілік бойынша ең таңғажайып нәтижелердің кейбіреулері NL және SL күрделілік классдарының толықтыру бойынша жабық екенін көрсетті, ал бұрын олар жабық емес деп есептелді (Immerman–Szelepcsényi теоремасын қараңыз). Соңғысы қазір біз SL L-ге тең екенін білгенде таңқаларлық емес, бұл детерминистік класс. Өз-өзіне төмен кез келген класс толықтыру бойынша жабық.
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem. One can generalize this to the complement of a complexity class, called the complement class, which is the set of complements of every problem in the class. If a class is called C, its complement is conventionally labelled co C. Notice that this is not the complement of the complexity class itself as a set of problems, which would contain a great deal more problems. A class is said to be closed under complement if the complement of any problem in the class is still in the class. Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class. However, under many one reductions, many important classes, especially NP, are believed to be distinct from their complement classes (although this has not been proven). The closure of any complexity class under Turing reductions is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement. Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases. Similarly, probabilistic classes such as BPP, ZPP, BQP or PP which are defined symmetrically with regards to their yes and no instances are closed under complement. In contrast, classes such as RP and co RP define their probabilities with one sided error, and so are not (currently known to be) closed under complement. Some of the most surprising complexity results shown to date showed that the complexity classes NL and SL are in fact closed under complement, whereas before it was widely believed they were not (see Immerman–Szelepcsényi theorem). The latter has become less surprising now that we know SL equals L, which is a deterministic class. Every class which is low for itself is closed under complement.