Den komplexa klass PP består av alla beslutsproblem som kan lösas av polynom-tid probabilistiska Turing maskiner. Det är väl känt att PP är en mycket svårhanterlig komplexitetsklass och att PP-kompletterande problem med all sannolikhet är svårare än NP-kompletta problem. Vi undersöker förekomsten av fasövergångar för en familj av PP completive Boolean tillfredsställande problem enligt den fasta klausuler-till-variables-förhållandet modell. En typisk medlem av denna familj är beslutsproblemet #3SAT( 3⁄4  på 3⁄4 ): givet en 3CNF-formula, är det tillfredsställt med åtminstone kvadratroten av det totala antalet möjliga sanningsuppdrag? Vi ger bevis för att det finns ett kritiskt förhållande Ö ¿ 3⁄4 där den asymptotiska sannolikheten för # 3SAT ( 3⁄4  och 3⁄4 ) genomgår en fasövergång från 1 till 0. Vi får övre och nedre gränser för Ö ¿ 3⁄4
Bailey et al undersöka förekomsten av fasövergångar för en familj av PP-fullständiga problem-#SAT problem REF.
Phase Transitions of PP-Complete Satisfiability Problems
{'venue': 'PROC. 17TH IJCAI-2001', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}