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.



Complexity of a Diophantine equation having $\leq1$ solutions
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**](http://dx.doi.org/10.1016/0304-3975(86)90135-0), Theor. Comput. Sci. 47, 85-95 (1986). [ZBL0621.68030](https://zbmath.org/?q=an:0621.68030).


