# Why does the proof that #SAT is in IP stop after m rounds?

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.

Thanks!

• Is the polynomial multivariate by any chance? – Yuval Filmus Apr 29 '17 at 10:25
• A multivariate polynomial of degree $d$ can have more than $d$ roots. Consider for example $x_1 - x_2$. – Yuval Filmus Apr 29 '17 at 10:46
• 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? – D.W. Apr 29 '17 at 16:00
• 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. – user2756154 Apr 30 '17 at 14:31