If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root, and "satisfiable" if it is 1. (I use interpolating in a very loose sense here). It seems plausible that the degree/number of turning points of the resulting polynomial corresponds loosely to how "complex" the formula is.

To give a trivial example,

$a \oplus b$ is quardratic, $(1-ab)(1-(1-a)(1-b))$


$a \wedge b$ is $ab$, linear.

I believe an argument of this sort was used by Smolensky to show that PARITY is not in $AC^0$. I wonder, however, if there is there a more precise interpretation of

  • The Degree of the Polynomial
  • The Number of Turning Points in the Polynomial?


  • $\begingroup$ What's a "turning point"? Do you mean critical point (a point where all partial derivatives are zero)? $\endgroup$ – Jeffε Dec 8 '10 at 22:15
  • $\begingroup$ @JeffE sorry about the lack of clarity. I actually mean a point where any of the partial derivatives are zero, and it is not a saddle point. I think this is intuitively the amount the polynomial "folds" $\endgroup$ – gabgoh Dec 9 '10 at 1:53
  • 2
    $\begingroup$ Ah. But there isn't a number of fold points. For a generic function on $n$ variables, the set of points where (say) the first partial derivative is zero is a collection of disjoint $(n-1)$-dimensional manifolds in $\mathbb{R}^n$, not a finite set of points. $\endgroup$ – Jeffε Dec 9 '10 at 3:09
  • $\begingroup$ @JeffE Good point. I think the second part of my problem isn't well posed. Intuitively, there seems to be a way to characterize how much a polynomial "twists", but I'm not sure what that is. I'll have to think about it more. I have edited it out of my question. $\endgroup$ – gabgoh Dec 9 '10 at 6:24
  • $\begingroup$ Maybe you meant the number of local extrema? $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 20:35

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.