Skip to main content
Computer Science

Return to Answer

Post Timeline

According to the remark of David Richerby, I make this modification to clarify the relation of the Entscheidungsproblem and Hilbert's tenth problem. Thanks!
Source Link
yu LI
yu LI
  • 21
  • 2

I try to provide more details for my above answer.

In fact, this question is a dilemma problem.

TheOn one hand, the Diophantine Equation Problem (DEP) is undecidable according to Turing’s EntscheidungsproblemMatiyesevich’s theorem (that isMatiyesevich’s theorem answers Hilbert's tenth problem, and Turing’s Halting problem answers the answer togeneralization 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 (verifiabledecidable 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 is not correctneeds to be questioned.

I try to provide more details for my above answer.

In fact, this question is a dilemma problem.

The Diophantine Equation Problem (DEP) is undecidable according to Turing’s Entscheidungsproblem (that is the answer to Hilbert's tenth problem); but there isn't any undecidable problem in NP according to the definition of NP (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 it is not correct.

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.

Source Link
yu LI
yu LI
  • 21
  • 2

I try to provide more details for my above answer.

In fact, this question is a dilemma problem.

The Diophantine Equation Problem (DEP) is undecidable according to Turing’s Entscheidungsproblem (that is the answer to Hilbert's tenth problem); but there isn't any undecidable problem in NP according to the definition of NP (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 it is not correct.