Why isn't this undecidable problem in NP?

Question

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia:

NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that are] verifiable in polynomial time by a deterministic Turing machine.

[...]

A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Now consider the following problem:

Given a Diophantine equation, does it have any integer solutions?

Given a solution, it's easy to verify in polynomial time that it really is a solution: just plug the numbers into the equation. Thus, the problem is in NP. However, solving this problem is famously known to be undecidable!

(Similarly, it seems the halting problem should be in NP, since the "yes"-solution of "this program halts at the N-th step" can be verified in N steps.)

Obviously there's something wrong with my understanding, but what is it?

Answer 1

An equivalent definition of NP is that it consists of all problems that are decidable (not just verifiable) in polynomial time by a non-deterministic Turing machine. NTMs are known to be no more powerful than TMs in the sense that the set of problems decidable by NTMs is identical to the set of problems decidable by TMs, so clearly by this definition there can be no undecidable problems in NP.

To demonstrate that the two definitions of NP are equivalent, given the existence of a deterministic verifier you can demonstrate that a non-deterministic decider exists, and vice versa.

Say you have a deterministic polynomial verifier. Then there is also a machine that non-deterministically guesses a certificate of a length bounded by the polynomial corresponding to the certificate size bound of this problem/verifier and then runs the verifier. Since the alphabet is finite, the certificate for any given input is finite (and at most polynomial in the size of the input), and the verifier runs in polynomial time, the machine halts on all branches for all input and runs in (non-deterministic) polynomial time. Thus there is a non-deterministic decider for every deterministic verifier.

If you have a non-deterministic decider, then for every accepting computation you can write down the path of choices taken by the decider to reach the accept state. Since the decider runs in polynomial time, this path will be of at most polynomial length. And it's easy for a deterministic TM to validate that such a path is a valid path through an NTM to an accept state, so such paths form certificates for a polynomial time verifier for the problem. Thus there is a deterministic verifier for every non-deterministic decider.

Thus any undecidable problem cannot have a verifier that works on certificates of polynomial size (otherwise the existence of the verifier would imply the existence of a decider).

---

When you claim that a verifier exists for the halting problem, the certificate you're talking about is some encoding of (TM, I, N), where the TM halts on input I in N steps. This can indeed be verified in N steps, but the size of the certificate is not polynomial in the size of the (TM, I) input to the original problem (the halting problem); N can be arbitrarily large (regardless of encoding). If you try to convert such a verifier to a non-deterministic decider, you end up with a somewhat interesting machine. You should be able to prove that when run on (TM, I) for a TM that doesn't halt on input I no non-halting paths through the machine exist, but also that for any path leading to a halting state there is always another longer path (corresponding to a guess of a larger N), and thus there is no finite bound on its execution time. Essentially this is because there is an infinite space that needs to be explored by the initial non-deterministic guess. Converting such an NTM to a deterministic TM leads to one of those machines that neither loops nor halts on some input. In fact no NTM exists that can decide the halting problem, and so there is no verifier that works on certificates with a bounded size.

I'm not so familiar with Diophantine equations, but it looks like essentially the same problem applies to your argument there.

For this reason I find it easier to reason about the NTM definition of NP. There are verifiers for problems that are undecidable (just not ones that work on certificates that have a polynomial size bound in the size of the input to the original problem). In fact any TM that recognises but does not decide some language can be easily converted into a verifier for the same language.

If you do think about verifiers, I suppose you have to give their time bounds in terms of the size of the original problem input, not in terms of the certificate size; you can arbitrarily inflate the size of certificates so that the verifier runs in a lower time bound in terms of the size of the certificate.

Answer 2

I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem.

Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x_1,...,x_k)$ such that $n \in S$ only if there exists integer coefficients $x_1$,..,$x_k$ such that $f(n;x_1,...,x_k) = 0$. In particular, the halting problem is a typical RE set, and so solving the above problem is undecidable.

Note that $x_1, ... x_k$ are not bounded in size, and in general can be arbitrarily large, so there is no "polynomial sized certificate" evident in this problem.

To expand: the integers $x_1, ... , x_k$ need to be written in binary to be a certificate. Since these integers can be arbitrarily large (regardless of $n$), we have that the certificate is not polynomial in $\log n$ or more importantly, not bounded by and computable function.

Every problem in $\mathsf{NP}$ however, has a certificate that is bounded by some polynomial $p(N)$ (where $N$ is size of input). So $\mathsf{NP}$ questions are trivially decidable, since you can enumerate every possible bit string upto length $p(N)$ and if none of them certify the input, return false. If some does then return true.

Answer 3

You should have scrolled down to the formal definition:

A language $L$ is in NP if and only if there exist polynomials $p$ and $q$, and a deterministic Turing machine $M$, such that

• For all $x$ and y, the machine $M$ runs in time $p(|x|)$ on input $(x,y)$.
• For all $x \in L$, there exists a string $y$ of length $q(|x|)$ such that $M(x,y) = 1$.
• For all $x \not\in L$ and all strings $y$ of length $q(|x|)$, $M(x,y) = 0$.

That is, a verifier has to work also on non-solutions. Somewhere in there , undecidable problems fail (in your case, the length restriction of solution candidates is probably not fulfilled), as is obvious by the (in the computability sense) more clearer definition:

NP is the set of decision problems decidable by a non-deterministic Turing machine that runs in polynomial time.

Answer 4

I try to provide more details for my above answer.

In fact, this question is a dilemma problem.

On one hand, the Diophantine Equation Problem (DEP) is undecidable according to Matiyesevich’s theorem (Matiyesevich’s theorem answers Hilbert's tenth problem, and Turing’s Halting problem answers the generalization of Hilbert's tenth problem, that is, the Entscheidungsproblem); but on the other hand, there isn't any undecidable problem in NP according to the definition of NP (decidable and verifiable).

That is to say, either DEP is not in NP, or DEP is in NP. Both of them concern the definition of NP.

If DEP is not in NP, that means problems in NP (NDTM＝NonDeterminstic Turing Machine) are decidable and verifiable, that is to say we accept P=NP (NDTM).

If DEP is in NP, then NP (NTM＝Non Turing Machine) contains decidable and undecidable, obviously decidable is verifiable, therefore the problem is whether undecidable is verifiable? In fact, that is the famous problem of P vs. NP. Certainly, undecidable is unverifiable, so NP corresponds to NTM (Non Turing Machine) instead of NDTM (NonDeterminstic Turing Machine).

Going on the premise of DEP is in NP (NTM), we think that the NP (NTM) is Nondeterministic Problem (undecidable), and the current definition of NP (NDTM, decidable and verifiable) has lost this nondeterminism (undecidable), so we think that it needs to be questioned.

Answer 5

We think that the dilemma you raised about Diophantine equation is very significant, because it reveals something abnormal in the current definition of NP : - A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Concerning the definition of NP, it can be traced to the 60’s, where a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, in order to recognize these problems from those problems solvable in Polynomial time (P), the concept of NP was put out.

However, the current definition of NP defined as verifiable in polynomial time confuses NP with P, because a problem in P is also verifiable in polynomial time. In another word, such definition leads to the loss of the essence of NP, « nondeterminisme ». Consequently, it causes serious ambiguities in understanding NP, for example, your dilemma : by nature the problem of Diophantine equation is undecidable; but by the definition of NP, it is decidable, …

In our opinion, the difficulty in solving « P versus NP » lies firstly at cognition level, so if we hope to get an insight into « P versus NP », we need at first to question : What is NP?