# Complexity of a Diophantine equation having $\leq1$ solutions

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.

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

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.
• 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$. – 1.. Apr 19 at 0:07
• @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 – Will Sawin Apr 19 at 0:40
• @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. – Will Sawin Apr 19 at 0:46