PH klass

Komplexitetsklass PH (från den engelska  polynomhierarkin ) - föreningen av alla komplexitetsklasser från polynomhierarkin :

Således tillhör ett predikat klassen PH om det finns k så att predikatet tillhör klassen eller . Det sägs också att språket som känns igen av ett sådant predikat (det vill säga mängden av alla ord för vilka predikatet returnerar 1) tillhör klassen PH.

Motsvarande definitioner

Logisk karaktärisering

Klassen av språk PH är exakt densamma som den klass av språk som kan uttryckas med andra ordningens logik .

Spelkarakterisering

Vi kallar följande struktur för ett ändligt spel . Det finns ett träd vars hörn är märkta med namnen på två spelare A och B (alla hörn på samma nivå är märkta med samma namn, dragen växlar), och kanterna motsvarar spelarnas drag. Låt ett första ord x ges — spelets initiala konfiguration. Då är antalet nivåer i trädet (det vill säga antalet drag) lika med någon funktion f av längden x , och varje kant är märkt med ett ord med längden g av längden x (spelarens drag är det ord som märker kanten). Det finns ett predikat från den initiala konfigurationen och sekvensen av spelarnas drag, som avgör vem som vann (om det är lika med 1, så vann den första spelaren). Eftersom spelet är ändligt, har antingen den första spelaren eller den andra alltid en vinnande strategi. Låt oss kalla ett spel som känner igen språket L om för varje ord x från L spelare A har en vinnande strategi.

Klassen PH är klassen av alla språk som känns igen av spel så att f är en konstant (dvs antalet drag i spelet är fast och inte beror på längden på inmatningsordet) och g är ett polynom i längd x (alltså, från varje vertex av trädet, förutom den sista, fortsätter längs kanterna, där är detta polynom).

Stängning

Till skillnad från klasserna i polynomhierarkin som utgör klassen PH, är det säkert känt att PH är stängt under skärningspunkten, föreningen och komplementet mellan språk. Detta betyder att om språken och tillhör PH, så hör språken till PH .

För att bevisa det räcker det att presentera spel som känner igen dessa kombinationer av språk, om det finns spel som känner igen och . För komplementet, låt oss överföra rätten till det första draget till en annan spelare och ta . För att skära varandra tar vi två spel som känner igen och , så att antalet drag i dem är detsamma, och det andra startar inte av spelaren som gör det sista draget i det första. Efter det lägger vi till det andra spelet till varje slutpunkt av det första spelet och tar som utdelningspredikat , där och är uppdelningen av hela sekvensen av drag i två delar: delen som motsvarar det första spelet och delen som motsvarar till den andra. För att förenas tar vi spel som känner igen och , med samma antal drag och samma första spelare. Låt oss skapa ett nytt hörn som motsvarar en annan spelare och fästa ett träd i det första spelet (vi skriver ordet 00...0 ovanför denna kant) och de återstående kanterna i det andra spelet. Vi betecknar det första ordet i spelet med z , och resten av ordföljden med , och tar som payoff-predikat .

Relationer med andra klasser

Per definition inkluderar klassen PH alla klasser i polynomhierarkin, inklusive P och NP . Dessutom innehåller den probabilistiska klasser, såsom BPP-klassen (eftersom BPP finns i klassen ). Själva PH-klassen ingår i PSPACE-klassen och P PP -klassen (en klass av problem som löses i polynomtid på en Turing-maskin med tillgång till PP -klassens oracle ).

Öppna nummer

Det är fastställt att P = NP om och endast om P = PH. Detta påstående kan göra det lättare att bevisa att P ≠ NP (om så är fallet), eftersom det bara skulle vara nödvändigt att skilja P från en mer allmän klass än NP.