⊕P кешендігі туралы: Полиномдық уақытта шешілетін, қабылдау жолдарының саны тақ болса жауап беретін есептер класы. ⊕SAT толық проблемасы, теориялық мағлұмат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік күрделілік теориясында, күрделілік класы ⊕P (айтылуы: "паритет P") – бұл полиномдық уақытта нон-детерминистік Тьюринг машинасымен шешілетін шешім проблемаларының класы, мұнда қабылдау шарты – қабылдайтын есептеу жолдарының саны тақ болуы керек. ⊕P проблемасының мысалы: "берілген графтың толық сәйкестіктерінің саны тақ па?". Бұл класс 1983 жылы Пападимитриу және Закос есімді ғалымдар анықтаған. ⊕P толық проблемасының мысалы (көптеген бір редукциялар бойынша) ⊕SAT: берілген Буль формуласы үшін, оның қанағаттандыратын тапсырмаларының саны тақ па? Бұл Кук-Левин теоремасынан туындайды, себебі редукция үнемді. ⊕P – санау класы, және оны сәйкес #P проблемасына жауаптың ең кіші маңызды битін табу ретінде қарастыруға болады. Ең жоғары маңызды бит табу мәселесі PP класында. PP класы ⊕P класынан әлдеқайда қиын деп есептеледі; мысалы, 1998 жылы Beigel, Buhrman және Fortnow көрсеткендей, P = ⊕P ≠ NP = PP = EXPTIME болатын салыстырмалы әлем бар (оракул машинасына қараңыз). Тода теоремасы PPP класының құрамында PH класы бар екенін көрсетсе де, P⊕P класының NP класын қамтитыны белгісіз. Дегенмен, Тода теоремасының дәлелінің бірінші бөлігі BPP⊕P класының PH класын қамтитынын көрсетеді. Ланс Фортноу осы теореманың қысқаша дәлелін жазған. ⊕P класы граф автоморфизмі мәселесін қамтиды, және шындығында бұл мәселе ⊕P класы үшін төмен. Сонымен қатар, ол UP класын тривиальды түрде қамтиды, себебі UP класындағы барлық мәселелердің қабылдайтын жолы нөл немесе бір ғана болады. Жалпы алғанда, ⊕P класы өзі үшін төмен, яғни мұндай машина кез келген ⊕P мәселесін бірден шеше алудан ешқандай артық күш алмайды. Класс атындағы ⊕ символы Буль алгебрасындағы ⊕ символының эксклюзивті дизъюнкция операторын білдіру үшін қолданылуына сілтеме болуы мүмкін. Бұл түсінікті, себебі егер "қабылдайды" дегенді 1 деп, ал "қабылдамайды" дегенді 0 деп қарастырсақ, машинаның нәтижесі – әрбір есептеу жолының нәтижелерінің эксклюзивті дизъюнкциясы болады.
In computational complexity theory, the complexity class ⊕P (pronounced "parity P") is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. An example of a ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983. An example of a ⊕P complete problem (under many one reductions) is ⊕SAT: given a Boolean formula, is the number of its satisfying assignments odd? This follows from the Cook–Levin theorem because the reduction is parsimonious. ⊕P is a counting class, and can be seen as finding the least significant bit of the answer to the corresponding #P problem. The problem of finding the most significant bit is in PP. PP is believed to be a considerably harder class than ⊕P; for example, there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME, as shown by Beigel, Buhrman, and Fortnow in 1998. While Toda's theorem shows that PPP contains PH, P⊕P is not known to even contain NP. However, the first part of the proof of Toda's theorem shows that BPP⊕P contains PH. Lance Fortnow has written a concise proof of this theorem. ⊕P contains the graph automorphism problem, and in fact this problem is low for ⊕P. It also trivially contains UP, since all problems in UP have either zero or one accepting paths. More generally, ⊕P is low for itself, meaning that such a machine gains no power from being able to solve any ⊕P problem instantly. The ⊕ symbol in the name of the class may be a reference to use of the symbol ⊕ in Boolean algebra to refer the exclusive disjunction operator. This makes sense because if we consider "accepts" to be 1 and "not accepts" to be 0, the result of the machine is the exclusive disjunction of the results of each computation path.