Кіріспе
Күрделілік класы
#P толық проблемалары (оларды "шарпы P толық" немесе "сан P толық" деп атайды) есептеу күрделілігі теориясындағы күрделілік класын құрайды. Бұл күрделілік класындағы проблемалар келесі екі қасиетімен анықталады: Проблема #P класында, яғни көпмүшелік уақыттағы детерминистік емес Тьюринг машинасының қабылданатын жолдарының санын санау арқылы анықталатын проблемалар класы. Проблема #P қиын, яғни #P класындағы кез келген басқа проблема оған Тьюринг редукциясы немесе көпмүшелік уақыт санау редукциясы арқылы келтіріледі. Санау редукциясы – бұл басқа проблеманың кірістерінен берілген проблеманың кірістеріне және берілген проблеманың шығыстарынан басқа проблеманың шығыстарына көпмүшелік уақыттағы түрлендірулер жұбы, бұл басқа проблеманы берілген проблеманың кез келген ішкі процедурасын қолдану арқылы шешуге мүмкіндік береді. Тьюринг редукциясы – бұл берілген проблеманың ішкі процедурасына көпмүшелік санымен шақырулар жасайтын және осы шақырулардан басқа көпмүшелік уақытты пайдаланатын басқа проблеманың алгоритмі. Кейбір жағдайларда, нақты шешімдер санын сақтайтын, редукцияның нақты түрі – үнемді редукциялар қолданылады. #P толық проблемалары кем дегенде NP толық проблемаларымен бірдей қиын. #P толық проблеманы шешуге арналған көпмүшелік уақыт алгоритмі, егер ол болса, P және NP тең екенін көрсете отырып, P және NP мәселесін шешер еді. Мұндай алгоритм белгілі емес, сондай-ақ мұндай алгоритмнің жоқ екенін дәлелдейтін нәрсе де белгілі емес.
The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial time non deterministic Turing machine. The problem is #P hard, meaning that every other problem in #P has a Turing reduction or polynomial time counting reduction to it. A counting reduction is a pair of polynomial time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial time. In some cases parsimonious reductions, a more specific type of reduction that preserves the exact number of solutions, are used. #P complete problems are at least as hard as NP complete problems. A polynomial time algorithm for solving a #P complete problem, if it existed, would solve the P versus NP problem by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist.
Қатты санау нұсқаларындағы оңай мәселелер
Кейбір #P толық проблемалары оңай (полиномдық уақыт) проблемаларымен сәйкес келеді. Бульдық формуланың ДНҚ-да қанағаттандырылуын анықтау оңай: мұндай формула қанағаттандырылатын болса және қанағаттандырылатын конъюнкцияны (айнымалы және оның жоқтығы жоқ конъюнкция) қамтитын болса ғана қанағаттандырылады, ал қанағаттандыратын тапсырмалардың санын санау #P толық. Сонымен қатар, 2-қанағаттандырылатындықты шешу, қанағаттандыратын тапсырмалардың санын санауға қарағанда оңай. Топологиялық реттеу, топологиялық реттеулердің санын санауға қарағанда оңай. Бір толық сәйкестікті полиномдық уақытта табуға болады, бірақ барлық толық сәйкестіктерді санау #P толық. Толық сәйкестіктерді санау мәселесі Лесли Валианттың 1979 жылғы мақаласында #P толық екендігі көрсетілген оңай P мәселесіне сәйкес келетін алғашқы санау мәселесі болды, ол сондай-ақ #P класын және #P толық проблемаларын алғаш рет анықтады.
Тақырыбы
Кейбір #P толық проблемаларына жоғары ықтималдықпен жақсы жуықтама беретін ықтималдық алгоритмдер бар. Бұл – ықтималдық алгоритмдердің күшін көрсететін мысалдардың бірі. Көптеген #P толық проблемалары үшін толық полиномиалдық уақытты кездейсоқ жуықтау схемасы, немесе "FPRAS" бар, ол бейресми түрде, проблеманың мөлшеріне және қажетті дәлдік деңгейіне қатысты полиномиалдық уақытта, кез келген дәлдік деңгейіне жуықтап, жоғары ықтималдықпен нәтиже береді. Джеррум, Валиант және Вазирани, әрбір #P толық проблемасы FPRAS-қа ие екенін немесе оны жуықтау принципиалды түрде мүмкін емес екенін көрсетті; егер #P толық проблемасын дәл жауаптың кіріс мөлшеріне қатысты полиномиалдық қатынаста тұрақты түрде жуықтайтын полиномиалдық уақыт алгоритмі болса, онда осы алгоритмді FPRAS құру үшін пайдалануға болады.