patternMajor
Why isn't this undecidable problem in NP?
Viewed 0 times
thisproblemwhyundecidableisn
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#1887, answer score: 29
Revisions (0)
No revisions yet.