Timeline for Proving NP complexity
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2012 at 0:35 | comment | added | goat | You must be right. I thought I read my claim somewhere, but I can't find it. Thanks for straitening me out. | |
| Dec 1, 2012 at 20:54 | comment | added | user541686 | @rambocoder: I believe if the Hamiltonian path is not valid, then that must still be decidable in P-time. What doesn't have to be decidable in P-time is verifying that there doesn't exist such a path, if someone comes along and tells you there isn't. | |
| Dec 1, 2012 at 20:41 | comment | added | goat | I'm a bit confused too, but i feel the subtlety is in the word "verifiable". if the ham path is truely valid, then a verification algo must be able to confirm that particular paths validity in poly time. if the ham path is not valid, then, the verification algo can take longer than poly time to report invalidity(maybe it never needs to report?). | |
| Dec 1, 2012 at 20:21 | comment | added | user541686 | @rambocoder: I think you're confusing something here (or maybe I worded my answer poorly). If someone gives you a graph and says "is there a Hamiltonian cycle in this graph?" then a "no"-type answer is indeed believed to be not verifiable in P-time. But the question of "is this particular path indeed a Hamiltonian cycle?" is indeed verifiable in P-time, whether the answer is "yes" or "no". I think you're talking about the former, whereas I'm talking about the latter... or maybe I'm just confused? | |
| Dec 1, 2012 at 20:19 | comment | added | goat | I think his statement was wrong. I think isInNp = (plug23AndEvaluateTookPolyTime && plug23EvaluatedTo55) || !plug23EvaluatedTo55; is correct. I think 23 is one of many instances. For other instances, like 24(which will not fulfill the equation), there is no restriction on how long it takes to eval/verify it. | |
| Dec 1, 2012 at 19:55 | comment | added | user541686 | @rambocoder: Oh, now it's clearer what you mean. My answer isn't wrong, though, because I was referring to instances "of this problem" (i.e. the OP's example problem), which is clearly looking for a "yes"-type answer. He has to choose his example problem carefully of course, but as currently worded I think this is correct, right? | |
| Dec 1, 2012 at 19:50 | comment | added | goat | I believe the first paragraph on wikipedia conflicts with your answer. NP | |
| Dec 1, 2012 at 19:27 | comment | added | user541686 | @rambocoder: What do you mean by "yes" and "no", exactly? "Is there a path..." and "is there not a path..." obviously have opposite answers, but they're asking the same question... | |
| Dec 1, 2012 at 16:26 | comment | added | goat | I thought only a "yes" answer needed to be verifiable in poly time for a problem to be in NP? If the answer is "no", it could run forever and still be in NP. Is my understanding wrong? I'm referring to a deterministic machine. | |
| Dec 1, 2012 at 8:05 | history | edited | amit | CC BY-SA 3.0 | added 21 characters in body |
| Dec 1, 2012 at 8:03 | comment | added | user541686 | @amit: Yeah I forgot to mention that, since it was already in the question... feel free to edit it if you'd like | |
| Dec 1, 2012 at 7:57 | comment | added | amit | However - note that the answer is still not complete, a problem is in NP if you can check the correctness of every correct and every incorrect answer for every instance of this problem in polynomial time. | |
| Dec 1, 2012 at 7:49 | history | edited | amit | CC BY-SA 3.0 | added 1 characters in body |
| Dec 1, 2012 at 7:46 | comment | added | user541686 | @amit: ...who was talking about NP-completeness in the first place? | |
| Dec 1, 2012 at 7:43 | comment | added | amit | NO! You are describing an algorithm not a problem! NP-Completeness is defined on problems not algorithms. A problem is NP-Complete if and only if it is: (1) In NP. (2) has a polynomial reduction from each problem in NP. | |
| Dec 1, 2012 at 6:12 | vote | accept | roverred | ||
| Dec 1, 2012 at 4:56 | history | answered | user541686 | CC BY-SA 3.0 |