No, takze majme PCP( r, s )

To znamena, ze mame triedu problemov, pre ktore existuje verifikator V(x,ro,pi) ktory robi nasledovne:
- x je instancia problemu
- V bezi v case polynomialnom od |x|
- ro je postupnost r( |x| ) nahodnych bitov
- pi je dokaz
- pre kazde mozne ro sa V pocas vypoctu pozrie nanajvys na s( |x| ) bitov dokazu pi
(formalne, V je turingac co ma x na vstupnej paske, ma druhu pasku s random bitmi a tretiu pasku s bitmi dokazu, pricom na tretiu pasku vie robit random access na konkretne bity ak pozna ich index)

Pritom musi platit:
- ak x patri do jazyka, tak existuje dokaz pi taky, ze V(x,ro,pi) akceptuje pre kazde ro
- ak x nepatri do jazyka, tak pre kazdy dokaz pi je pravdepodobnost toho, ze V(x,ro,pi) akceptuje nanajvys 1/2
  inymi slovami, pre kazde pi nas k akceptovaniu dovedie najviac polovica vsetkych moznych ro

Je zjavne, ze P = PCP(0,0).

Zoberme teraz PCP( O(log n), 1 ), resp. PCP( O(log n), 2 ).
(Volajme ich "poduloha A" a "poduloha B".)
Je zjavne, ze toto su nadmnoziny PCP(0,0), takze nadmnoziny P.
Ak chceme ukazat, ze su rovne P, potrebujeme teda dokazat opacnu inkluziu 
-- teda ze existencia prislusneho verifikatora implikuje existenciu polynomialneho algoritmu

Majme teda konkretny verifikator.
Ako z neho zostrojit nas polynomialny algoritmus?
Zacneme tym, ze hrubou silou odskusame vsetky mozne postupnosti nahodnych bitov.
Kedze V pouziva O(log n) nahodnych bitov, je len O(poly(n)) moznosti, ake to su.
Pre kazdu z nich si odsimulujeme verifikator (mozeme, lebo bezi v poly(n) case).
Zistime, na ktory 1, resp. 2, bity dokazu by sa pozrel.
Opat, vyskusame vsetky 2, resp. 4, moznosti, ake maju hodnoty
Pre kazdu z tychto moznosti zistime, ci verifikator akceptuje.

Toto cele prebehlo v polynomialnom case.
No a teraz sme si zozbierali informacie ktore (v podulohe A) vyzeraju napr. nasledovne:
1. ak su nahodne bity 0010 a v dokaze je 47. bit rovny 0 tak V akceptuje
2. ak su nahodne bity 0011 a v dokaze je 23. bit lubovolny tak V akceptuje
3. ak su nahodne bity 1101 a v dokaze je 47. bit rovny 1 tak V akceptuje
4. ak su nahodne bity 1111 tak V neakceptuje nech je v dokaze 599. bit lubovolny
5. ...

Riesenie podulohy A je teraz jednoduche. 
Akceptovat chceme ak existuje taky dokaz, pre ktory kazda postupnost nahodnych bitov vedie k akceptacii. 
To znamena, ze jednoducho priamo pocas toho, ako iterujeme cez vsetky moznosti nahodnych bitov, si znacime, co uz o dokaze vieme.
Ak niekedy narazime na spor, tak zamietneme, a ak nie, tak na konci akceptujeme.
(Su dve moznosti sporu, bud nastane vyssie uvedena situacia typu 4, alebo nastane naraz situacia typu 1 a 3, kde 
rozne postupnosti nahodnych bitov potrebuju aby na *tom istom* policku dokazu bola rozna hodnota.)

Riesenie podulohy B bude o cosi zlozitejsie.
Tam sme zozbierali informacie typu:
"ak su nahodne bity 0010, tak potrebujeme, aby 47. a 123. bit mali bud hodnoty (0,1) alebo hodnoty (1,1)".

To, co teraz potrebujeme rozhodnut (deterministicky a v polynomialnom case), je, ze ci existuje dokaz,
ktory vsetky tieto podmienky splna.

Toto je nieco podobne ako 2-SAT a teda to vieme riesit v polynomialnom case.
Presnejsie, prevedieme to na 2-SAT.
Pre kazdy bit dokazu, na ktory sa aspon jedna vetva vypoctu pozrela, si spravime jednu premennu.
No a kazda informacia typu "x. a y. bit nesmu mat naraz hodnoty (p,q)" nam vyrobi jednu 2-SAT klauzulu.