2
$\begingroup$

Let's define the following languages over the alphabet $\Sigma=\{0,1\}$:

H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, i.e. there exists a root/solution in $\Bbb{Z}^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

RH10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, each integer in the closed interval $[-2^n,2^n]$ or in other words there exists a root/solution in $[-2^n,2^n]^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

If RH10 can be solved in deterministic polynomial time, does this imply that H10 is decidable? If there is a polynomial-time algorithm for RH10, then it can't be enumerating all possible solutions in $[-2^n,2^n]^n$ (there are too many of them to try in polynomial time), so it seems like it must somehow find solutions regardless of how large they are, and thus also be able to solve H10 too. Is that right? Does it follow from this that $P$ is unequal to $NP$, as H10 is known to be, in fact, undecidable?

$\endgroup$
6
$\begingroup$

No.

If I follow you correctly, your argument is that if P=NP, then $\mathrm{RH}10\in \mathrm{P}$ and the same procedure would be a valid algorithm for $\mathrm{H}10$, which contradicts with the fact that $\mathrm{H}10$ is undecidable.

The step that lacks proof is the claim that the implication:

if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

To see that this claim doesn't follow, consider what a polynomial algorithm to solve $\mathrm{RH}10$ could be doing. We only know it lies in P somehow, so let's assume it runs in $O(n^k)$ time for some $k\in\mathbb{N}$. Let $l$ be such that we can verify whether a value is a solution for a Diophantine equation with $n$ variables in $O(n^l)$ time.

It is possible that this is done by the following algorithm $A$, given an instance $I$ of $\mathrm{RH}10$:

  1. Identify a set $S\subseteq [-2^n,2^n]^n$ of size $O(n^{k-l})$ in $O(n^k)$ time such that $s$ is a solution to the Diophantine equation encoded in $I$ if and only if $s\in S$.

  2. Iterate over all elements in $s\in S$ and test whether it is a solution of $I$. If a solution is found, report that $I$ has a solution, otherwise report it has not.

Observe that this is a valid algorithm to solve $\mathrm{RH}10$ in $O(n^k)$ if and only if there exist a procedure to carry out step 1. We don't know whether this is true, it is unlikely, but we don't know so it is at least possible.

Now, does the existence of algorithm $A$ give us a procedure to decide $\mathrm{H}10$? No. Algorithm $A$ requires that the solution values are restricted to some finite subset of $\mathbb{Z}^n$ to work. This is true even if we only use step 1. I hope it is clear that the existence of algorithm $A$ brings us no closer to deciding $\mathrm{H}10$.

Therefore, it is clear that the claim that

if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

is not motivated, as the possibility of the existence of algorithm $A$ is not dis-proven, while we have seen that the existence of algorithm $A$ contradicts your claim.

$\endgroup$

Your Answer

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