I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of degree $d$ can agree for at most $d$ values. As the proof in the Sipser text goes (which I believe is the standard proof), the degree of the polynomial is at most $n$. Why can't the verifier simply check $n+1$ points and prove with certainty whether $\langle\phi, k\rangle \in$ #SAT?

Would this require exponential time? I can't see how the Prover can escape the testing of $n+1$ points.


  • $\begingroup$ Is the polynomial multivariate by any chance? $\endgroup$ – Yuval Filmus Apr 29 '17 at 10:25
  • 1
    $\begingroup$ A multivariate polynomial of degree $d$ can have more than $d$ roots. Consider for example $x_1 - x_2$. $\endgroup$ – Yuval Filmus Apr 29 '17 at 10:46
  • 1
    $\begingroup$ When you say "the proof for #SAT", I doubt there is only one possible proof. Can you edit your question to include a summary of the particular interactive proof protocol you have in mind? $\endgroup$ – D.W. Apr 29 '17 at 16:00
  • $\begingroup$ The proof is somewhat lengthy (en.wikipedia.org/wiki/IP_(complexity)#.23SAT_is_a_member_of_IP), but it's the same proof that I find everywhere I look (Sipser, Papadimitriou, etc.). The polynomial is originally multivariate, since an assignment to SAT has $m$ variables, but the Prover alters the polynomial to make it univariate. $\endgroup$ – user2756154 Apr 30 '17 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.