For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can efficiently construct (using \emph{arithmetization}) a low-degree polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all points in the Boolean cube $\{0,1\}^n$; the constructed polynomial $p$ can be interpreted as a polynomial over an arbitrary field $\mathbb{F}$. The problem $\#SAT$ (of counting the number ... more >>>

We consider a class, denoted APP, of real-valued functions f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to within any epsilon>0, by a probabilistic Turing machine running in time poly(n,1/epsilon). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete ... more >>>