1
$\begingroup$

Given $3SAT$ formula $\phi$ in $n$ variables and a $\mu\in(0,1/2)$ what is the smallest degree of polynomial $f\in\mathbb Z[x_1,\dots,x_n]$ such that for an $(a_1,\dots,a_n)\in\{0,1\}^n$ if $\phi(a_1,\dots,a_n)=1$ then $|f(a_1\pm\delta,\dots,a_n\pm\delta)|>\frac12$ and if $\phi(a_1,\dots,a_n)=0$ then $|f(a_1\pm\delta,\dots,a_n\pm\delta)|<\frac12$ if $|\delta |<\mu$?

We know the degree cannot exceed $n$.

Improve this question
$\endgroup$
2
  • $\begingroup$ Probably $|\mu|<\delta$ at the end of the question should be $|\delta|<\mu$. $\endgroup$
    – Andreas Blass
    Commented Mar 29, 2019 at 23:48
  • $\begingroup$ @AndreasBlass Made modifications. $\endgroup$
    – VS.
    Commented Mar 30, 2019 at 0:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .