Timeline for answer to Why isn't this undecidable problem in NP? by yu LI
Current License: CC BY-SA 3.0
Post Revisions
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17, 2016 at 3:49 | comment | added | 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, … | |
| Feb 17, 2016 at 3:37 | comment | added | 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). | |
| Feb 17, 2016 at 3:05 | comment | added | 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. | |
| Feb 16, 2016 at 16:05 | comment | added | 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. | |
| Feb 16, 2016 at 15:52 | comment | added | 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. | |
| Feb 16, 2016 at 15:46 | comment | added | 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. | |
| Feb 16, 2016 at 15:14 | comment | added | 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. | |
| Feb 16, 2016 at 12:53 | comment | added | 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). | |
| Feb 15, 2016 at 18:09 | comment | added | 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. | |
| Feb 15, 2016 at 10:09 | comment | added | yu LI | @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！ | |
| Feb 14, 2016 at 18:06 | comment | added | David Richerby | 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. | |
| Feb 14, 2016 at 17:17 | review | Low quality posts | |||
| Feb 16, 2016 at 15:17 | |||||
| Feb 14, 2016 at 13:24 | review | Late answers | |||
| Feb 14, 2016 at 18:07 | |||||
| Feb 14, 2016 at 13:09 | review | First posts | |||
| Feb 14, 2016 at 17:13 | |||||
| Feb 14, 2016 at 13:05 | history | answered | yu LI | CC BY-SA 3.0 |