25
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 1. Keep in mind that the definition you are quoting is for decision problems. 2. Regarding your Diophantine example, you are not claiming that every system there exists a polynomial bound on the size of solutions, right? $\endgroup$ – Dmitri Chubarov May 17 '12 at 17:01
  • $\begingroup$ @Dmitri: Er, yes I am claiming that. The size of the solution is exactly the same as the size of the problem - if there are N unknowns, the solution contains N integers. And this is a decision problem - the integer solution (needed to verify the "yes" case) would be its certificate. $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '12 at 17:06
  • 19
    $\begingroup$ The question is, how big are the intgerers $\endgroup$ – Artem Kaznatcheev May 17 '12 at 17:08
  • 10
    $\begingroup$ @BlueRaja-DannyPflughoeft if you have an infinite alphabet to encode your integers then you are not in the standard setting of complexity theory any more. With a finite alphabet the size of the encoding grows with the value of an integer. $\endgroup$ – Dmitri Chubarov May 17 '12 at 17:11
  • $\begingroup$ A solution to the halting problem would just return "Yes", without giving a hint of how many steps to simulate for verification. $\endgroup$ – RemcoGerlich Sep 5 '16 at 7:53
10
$\begingroup$

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.

$\endgroup$
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Of course I understand what it means to "solve a diophantine equation" - you find numbers that satisfy the equation. I don't see why Matiyasevich's indecidability theorem or recursively enumerable sets need to be brought into the discussion. But I think that last paragraph could explain it... $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '12 at 17:15
  • 1
    $\begingroup$ Alright this new edit explains it - that also explains why the Halting problem is not in NP, since the steps it takes to halt could be arbitrarily large. Thanks! $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '12 at 17:17
  • $\begingroup$ My suggested edit was to remove the first two paragraphs. The first two paragraphs explain why Hilbert's 10th problem is undecidable, which is completely tangential to the question; they just detract from the rest of the answer (which is a great answer otherwise!). $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '12 at 21:59
  • $\begingroup$ @BlueRaja-DannyPflughoeft if the first paragraph insulted you, then I can remove it (although you did ask "what is wrong with my understanding?"). The second paragraph is necessary to set the problem up more formally since you don't in your question. $\endgroup$ – Artem Kaznatcheev May 17 '12 at 22:02
  • 3
    $\begingroup$ @BlueRaja-DannyPflughoeft It is best if questions and answers are self-contained. My second paragraph sets up the problem and explains what it means for this problem to be undecidable. My third paragraph gives the quick answer. My 4th and 5th paragraph expand on that in more detail. As far as I can tell, all paragraphs are necessary. $\endgroup$ – Artem Kaznatcheev May 17 '12 at 22:08
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "a verifier has to work also on non-solutions" - if you're saying the verifier needs to fail for non-solutions, it does already. If you're claiming that the verifier needs to be able to verify "no" answers, that is incorrect - that would be co-NP. And I'm already aware of the second definition, but I was confused on how it could be equivalent to the first, since one definition seems to admit the problem in the question, while the other doesn't. $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '12 at 17:22
  • $\begingroup$ @BlueRaja-DannyPlughoeft: My observation is: verifiers have to be able to refute non-solutions. If you are aware of this, please edit your question accordingly; it makes you look quite unknowledgable. $\endgroup$ – Raphael May 17 '12 at 17:25
  • $\begingroup$ It's trivially obvious that the verifier already refutes non-solutions: just plug the numbers into the equation and see if it holds. I'm afraid I don't understand what you're trying to get at. $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '12 at 17:33
  • $\begingroup$ @BlueRaja-DannyPlughoeft: The "definition" you quote does not specify this behaviour. $\endgroup$ – Raphael May 17 '12 at 18:06
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ No, the undecidability of DEP (Hilbert's tenth problem) wasn't shown until 1970, by Matiyesevich. The Entscheidungsproblem is not Hilbert's tenth problem; concerns the validity of formulae of first-order logic. And, once again, the P vs. NP problem is absolutely not a problem about whether undecidable problems are verifiable. $\endgroup$ – David Richerby Feb 18 '16 at 9:38
  • 1
    $\begingroup$ If you want to provide more details you should edit your original post. $\endgroup$ – Tom van der Zanden Feb 18 '16 at 12:06
  • $\begingroup$ @DavidRicherby Note that the answer given by Ben : « the set of problems decidable by NTMs is identical to the set of problems decidable by TMs ». Just in this sense, I think that the definition of NP confuses P with NP, and it leads to P=NP (NDTM). If this definition needs to be questioned, then other conclusions deduced from this definition, like the equivalence of a deterministic verifier and a non-deterministic decider, need also to be questioned. $\endgroup$ – Yu Li Feb 24 '16 at 4:30
  • $\begingroup$ @YuLi "it leads to P=NP (NDTM)." I have no idea what you mean by that. Also, I don't see the relevance of pointing out that TMs and NTMs decide the same languages. If they didn't decide the same languages, NTMs would be a completely unreasonable model of computation and it's hard to imagine that we'd care what they can compute in polynomial time. In complexity theory, we're taking a finer-grained view and asking about the computational resources required and the definition of NP doesn't confuse that at all. $\endgroup$ – David Richerby Feb 24 '16 at 4:57
  • $\begingroup$ @DavidRicherby Thanks, I have modified my answer according to your remark in order to clarify the relation of the Entscheidungsproblem and Hilbert's tenth problem. Concerning the question about the current definition of NP, it is difficult to discuss in several words. The objective of my answer is just to evoke some reflexions about this basic topic, … $\endgroup$ – Yu Li Feb 24 '16 at 5:49
-2
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ This seems to be an opinion piece about the definition of NP, not an answer to the question. The definition of NP is just fine. It doesn't confuse P with NP; rather, it acknowledges that P is a subset of NP. To me, it would be very unnatural if P were not a subset of NP. NP is a class of problems that can be solved within certain resource bounds. That necessarily includes a whole bunch of easy problems (P) that can be solved without coming close to the limit of the resources available. $\endgroup$ – David Richerby Feb 14 '16 at 18:06
  • $\begingroup$ @DavidRicherby P and NP have the common property of « certificate verifiable in polynomial time » , but this property is not the essence of NP. If this property is used to define NP, then P is a subset of NP, and NP has P as its subset (decidable) and itself (undecidable). Therefore, one would wonder whether NP is decidable or undecidable? Just like the above dilemma : whether is Diophantine equation undecidable or decidable? So my answer is to suggest to investigate this dilemma from the view of the definition of NP: verifiable, undecidable is unverifiable! $\endgroup$ – Yu Li Feb 15 '16 at 10:09
  • $\begingroup$ Problems in NP are decidable by definition: NP is the class of problems decided by nondeterministic Turing machines. It's easy to prove that this is exactly the same set of problems that have polynomial-length certificates that can be verified in polynomial time. If you're worried that problems in NP might not be decidable, then you've misunderstood something. $\endgroup$ – David Richerby Feb 15 '16 at 18:09
  • $\begingroup$ Yes, I am worried that problems in NP might not be decidable. You talk of the equivalence of the two definitions of NP : NP is the class of problems decided by nondeterministic Turing machines; NP is the class of problems having polynomial-length certificates verified in polynomial time. I doubt this equivalence, because the one is about the existence of algorithm to solve a problem and the other about the existence of solution for a problem. The dilemma about Diophantine Equation may be directly related to this equivalence (see more details of my argument: arxiv.org/abs/1501.01906). $\endgroup$ – Yu Li Feb 16 '16 at 12:53
  • 2
    $\begingroup$ @YuLi The equivalence of the two definitions of NP is so straightforward that it's taught in undergraduate complexity theory classes. I suggest not uploading to ArXiv if you don't understand the basics of the field. $\endgroup$ – David Richerby Feb 16 '16 at 15:52

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.