我们继续和大家分享在StackExchange网站上关于“丢番图方程的两难问题”的英语讨论，讨论的焦点和分歧还是集中在NP的定义上，也就是我们博客的主题。

在讨论中，网友们充分表达了以non-deterministic Turing machine定义NP的流行观点（注）：

－ 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.（这里的NTM指non-deterministic Turing machine，就是我们所说的NDTM）

对此，我们质疑：

－Since « deterministic and nondeterministic TMs computing/deciding the same languages », what is the interest to define NP by this nondeterministic TM? and what are differences between NP and P?

讨论还会继续，有兴趣的网友可以详参。  

＊＊＊＊＊＊

David Richerby ：

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.

Yu Li （柳渝）：

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).  

Raphael :

@DavidRicherby I agree that this does not answer the question, but it clearly attempts to do so. Hence, "not an answer" flags are not appropriate. Bad/incorrect answers should be downvoted.  

David Richerby :

@Raphael I disagree that it attempts to answer the question. It gives a history of NP and claims that the definition of NP that we use is incorrect. Nowhere does it address the question of why solving Diophantine equations is not in NP.

David Richerby :

@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.

Raphael :

@DavidRicherby It seems to me that the author thinks it's an answer, so it's an honest effort, however misguided. As I said, I think this is a case for downvoting, not flagging. If you still disagree, please reflag and I'll let the other mods handle it.

Yu Li （柳渝）:

@Raphael This is not an ordinary question, because it questions about some basic concepts of computational complexity theory, so any simply answer is not sufficient. You should listen at least what the author of the question and others think about my answer, before you judge it as Bad/incorrect answer.  

Yu Li （柳渝）:

@DavidRicherby I know well the equivalence of the two definitions of NP, I just doubt it. The use of NDTM to define NP can be traced to Cook’s famous paper in 1971, where his NDTM is not the actual one as TM with guessing module, but a mix of Oracle with TM. However, Oracle does not « guess » a certificate, but directly « find » a solution (see more details of my argument: arxiv.org/abs/1501.01910).  

Yu Li （柳渝）:

@DavidRicherby You said nowhere does it address the question of why solving Diophantine equations is not in NP. In my opinion, this is a very interesting remark! In other words you are also questioning the definition of NP in terms of the relation between decision problems and NP, …

Yu Li （柳渝）:

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.

David Richerby :

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.  

Yu Li （柳渝）:

@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.  

David Richerby :

@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.

Yu Li （柳渝）:

@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, …  

Yu Li （柳渝）:

@DavidRicherby Talking about languages decided by some models of computation, it concerns the study of the nature of underlying problems. If NP and P are the same languages, how can we identify out the properties of NP? Do not forge that, quand some problems called « NP » appeared, they were observed to have somethings different from P, …  

David Richerby :

If NP and P are the same languages, then there are no "properties of NP" that are different from "properties of P". But deterministic and nondeterministic TMs computing the same languages does not mean that P and NP are the same. You are very confused about this whole subject; I suggest that you spend some time reading textbooks and acquainting yourself with the basics. I don't have time to keep pointing out your misconceptions.

Yu Li （柳渝）:

@DavidRicherby In any domain of knowledge, the most basic concepts are usually the simplest, but in the time the most difficult. We really need to return to textbooks, and search the origin of basic concepts. Since « deterministic and nondeterministic TMs computing/deciding the same languages », what is the interest to define NP by this nondeterministic TM? and what are differences between NP and P? If someone is interested, welcome to continue the discussion.  

注：网友Ben在他给出的answer中详细阐述了流行的NP定义，参看讨论的完整版：关于“丢番图方程的两难问题”的英语讨论（1）