E-snob

špecifikácia: protokol efektívne rozpoznávajúci klamstvo

        veľmi sebavedomej strany

input: C tvrdí že y je najlepšia možná odpoveď
splňujúca isté efektívne overiteľné kritéria
  (chceme overiť či má C pravdu

kóduj tvrdenie "odpoveď x je lepšia než y" ako SAT formulu
a tú reprezentuj ako multipremenný polynóm Y(x) stupňa d=n^{O(n)}
kde x=x_1,...,x_n sú premenné pre možné odpovede dĺžky n
  (chceme overiť či pre každé 0/1 ohodnotenie x platí Y(x)=0
  (teda či \Sum_{x\in 2^n} Y(x) mod p = 0
  (kde p je fixné prvočíslo z intervalu (2^n,2^(2n)]

požiadaj C o koeficienty <d+1 stupňového polynómu
f(X):=\Sum_{x_2,...,x_n\in 2^(n-1)} Y(X,x_2,...,x_n)
ak C zašle polynóm h tž h(0)+h(1) mod p není 0 prehlas "C je podozrivé"
inak zvoľ náhodné r z intervalu {0,...,p-1}
a rekurzivne použi tento protokol na overenie toho či f(r)=h(r) mod p
až kým neohodnotíš všetky x_1,...,x_n

output: ak C nezaváha ani po ohodnotení všetkych x_1,...,x_n
            prehlas "C je dôverihodné" inak "C je nedôverihodné"

{ak y je najlepšia možná odpoveď, t.j. \Sum_{x\in 2^n} Y(x)=0
{ existuju odpovede ktorými nás o tom C môže presvedčiť
{inak je pravdepodobnosť že odhalíme C aspoň (1-d/p)^n
{ keďže polynóm f-h má nanajvýš d koreňov
{ a teda pri každej voľbe r nútime C pokračovať v klamaní
{ s pravdepodobnosťou aspoň 1-d/p

problém: je možné overiť či má C pravdu bez
žiadania aby riešilo viac než NP ulohy?