1
$\begingroup$

We are provided a single Diophantine equation $$f(x_1,\dots,x_n)=0$$ having degree $\geq2$ and having the promise it has $\leq1$ solutions in the set $\{0,\dots,m-1\}^n$ and $t$ is the number of terms in the polynomial.

We are to decide if $$|\{(x_1,\dots,x_n)\in\{0,1\}^n:f(x_1,\dots,x_n)=0\}|>0?$$

Is there a $\mathsf{poly}(mnt)$ algorithm for the problem?

If $m=2$ degree of every $x_1$ to $x_n$ can be reduced to $1$.

I think for general $m$ it should be in $\mathsf{poly}(mnt)$.


Valiant-Vazirani is applicable but unless $t=\mathsf{poly}(n)$ a $\mathsf{poly}(nt)$ algorithm cannot resolve $\mathsf{NP}$ versus $\mathsf{BPP}$. It is not clear $\mathsf{SAT}$ is Valiant-Vazirani reducible to a $\mathsf{PromiseDiophantine}$ problem of having $\leq1$ integral solutions.

$\endgroup$
1
  • $\begingroup$ It is not clear if $SAT$ reduces to $t=poly(n)$ situation. $\endgroup$ – 1.. Apr 19 at 0:12
4
$\begingroup$

If you could solve this problem in polynomial time, then NP would be contained in BPP, which is viewed as being approximately as unlikely as P = NP. Too see this, pick your favorite encoding of SAT into diophantine equations on $\{0,1\}^n$ (for instance, you can take $f$ to be a sum of squares of expressions corresponding to individual clauses), and apply the main result of Valiant, L. G.; Vazirani, V. V., NP is as easy as detecting unique solutions, Theor. Comput. Sci. 47, 85-95 (1986). ZBL0621.68030.

$\endgroup$
4
  • $\begingroup$ Notice $t$ could be very large compared to $n$ and number of terms is part of input and it is not clear if $t$ is say quasipolynomial in $n$. $\endgroup$ – 1.. Apr 19 at 0:07
  • $\begingroup$ @1.. The sum of squares of expressions for clauses approach makes $t$ proportional to the number of clauses (after reducing to 3SAT, say), which is counted in the size of the SAT instance, so it indeed gives a polynomial algorithm $\endgroup$ – Will Sawin Apr 19 at 0:40
  • $\begingroup$ @WillSawin I am not familiar on Sum of Squares expressions for clauses. Perhaps expand by little details in explanation? $\endgroup$ – 1.. Apr 19 at 0:41
  • 2
    $\begingroup$ @1.. For 3SAT, for the clause $(x_i \vee x_j \vee x_k)$, take $ (1 - (1-x_i)(1-x_j)(1-x_k))^2$ and then sum the corresponding expression over all the clauses. $\endgroup$ – Will Sawin Apr 19 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.