<p>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. </p>

<p>To give a trivial example, </p>

<p>$a \oplus b$ is quardratic, $(1-ab)(1-(1-a)(1-b))$
</p>

<p>while </p>

<p>$a \wedge b$ is $ab$, linear. </p>

<p>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</p>

<ul>
<li>The Degree of the Polynomial</li>
<li><strike> The Number of Turning Points in the Polynomial? </strike></li>
</ul>

<p>Thanks!</p>

CC BY-SA 3.0
2014-11-15T12:39:30.060Z
Both $ab$ and $(1-ab)(1-(1-a)(1-b))$ seem quadratic when $a^2=a$ and $b^2=b$.
Turbo
CC BY-SA 2.5
2010-12-08T22:15:37.867Z
What's a "turning point"?  Do you mean *critical point* (a point where all partial derivatives are zero)?
Jeffε
CC BY-SA 2.5
2010-12-09T01:53:51.307Z
@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"
gabgoh
CC BY-SA 2.5
2010-12-09T03:09:40.050Z
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.
Jeffε
CC BY-SA 2.5
2010-12-09T06:24:31.133Z
@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.
gabgoh
CC BY-SA 2.5
2010-12-12T20:35:36.997Z
Maybe you meant the number of local extrema?
Tsuyoshi Ito
<cc.complexity-theory><polynomials>
Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?
gabgoh
# Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?

(Asked by: username_0 on 2010-12-08)

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))$

while

$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?

Thanks!

**Tags:** cc.complexity-theory, polynomials
> **Comments:**
> **username_2**: What's a "turning point"?  Do you mean *critical point* (a point where all partial derivatives are zero)?  
> **username_0**: @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"  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: Maybe you meant the number of local extrema?  
> **username_1**: Both $ab$ and $(1-ab)(1-(1-a)(1-b))$ seem quadratic when $a^2=a$ and $b^2=b$.  

---

## 0 answers

