Timeline for answer to What's "P=NP?", and why is it such a famous question? by Dima
Current License: CC BY-SA 4.0
Post Revisions
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Apr 22, 2020 at 13:22 | history | suggested | Andrew Campbell | CC BY-SA 4.0 |
Fix small punctuation and grammar issues - wonderful answer btw!
|
| Apr 22, 2020 at 4:41 | review | Suggested edits | |||
| S Apr 22, 2020 at 13:22 | |||||
| Feb 4, 2018 at 1:49 | history | edited | Dima | CC BY-SA 3.0 |
deleted 1 character in body
|
| S Oct 4, 2016 at 5:05 | history | suggested | Rafael Eyng | CC BY-SA 3.0 |
Break the main paragraph in bullets that might help understanding. At least it does in my point of view, feel free to disagree =)
|
| Oct 4, 2016 at 2:39 | comment | added | Rafael Eyng | I still have one question: since NP is non-deterministic polynomial time, and P is not said to be non-deterministic, does this mean that P is then deterministic? | |
| Oct 4, 2016 at 2:37 | review | Suggested edits | |||
| S Oct 4, 2016 at 5:05 | |||||
| Nov 5, 2014 at 3:34 | comment | added | Millie Smith | Correction in the second to last paragraph: "we would be certain that there is no way to solve an NP Complete problem in polynomial time on a conventional computer", since P is a subset of NP and proving P != NP does not necessarily say anything about what problems in NP that are not NP-Complete are actually in P. | |
| Feb 19, 2011 at 13:43 | comment | added | Dima | @Steve Jessop: I have edited the part about NP-completeness. Please take a look if it is making sense now. | |
| Feb 19, 2011 at 13:42 | history | edited | Dima | CC BY-SA 2.5 |
added 388 characters in body
|
| Feb 19, 2011 at 13:33 | comment | added | Dima | @Steve Jessop: thanks for the clarification. You are right, my explanation of NP-complete is vague. My goal there was to give the practical implication of NP-completeness. | |
| Feb 19, 2011 at 10:45 | comment | added | Steve Jessop | It's true in practice that solving NP-complete problems takes greater than polynomial time on a real computer, but that's not what it means, it's just the current state of the art, as a consequence of the fact that P=NP is unknown. If anyone found a polynomial algorithm to solve any NP-complete problem, that would prove P=NP, and we know that hasn't happened because it would be in the news! Conversely if it was proved that P!=NP, then we could confidently say that no NP-complete problem is solvable in polynomial time. | |
| Feb 19, 2011 at 10:40 | comment | added | Steve Jessop | I like this answer, except that the definition of NP-complete at the end is vague/wrong. NP-complete means an NP problem X, such that any NP problem Y can be reduced to X by a polynomial reduction. A polynomial reduction means that any case of the problem Y can be solved by solving one or more cases of the problem X, and that counting each case of solving X as "1", Y would be P. So for example the problem "sort" can be polynomially reduced to the problem "partition", as in Quicksort. It turns out that there are lots of important NP-complete problems, for example subset-sum and 3-SAT. | |
| Aug 9, 2010 at 13:41 | history | edited | compie | CC BY-SA 2.5 |
fixed gammar
|
| Feb 11, 2009 at 8:01 | comment | added | 1800 INFORMATION | Stepping in way late to an argument which is way over my head, but as a laymen I found Dima's explanation easier to grok than explanations based on verifiability have been. But that's just me | |
| Nov 24, 2008 at 4:24 | history | edited | grom | CC BY-SA 2.5 |
Changed the first word in second paragraph from no to now
|
| Sep 27, 2008 at 21:39 | comment | added | HenryR | Re: emulating NDTMs with DTMs - the only difference is that NDTMs know 'instinctively' what choice to make at any branch point. You can simulate this behaviour by making every choice at branch points, through breadth-first search, and you'll eventually follow the same computation path as the NDTLM | |
| Sep 25, 2008 at 16:15 | comment | added | Dima | Well, with the TM explanation you start by proving that for any non-deterministic TM you can build a deterministic TM, which solves the same problem. Then you naturally ask the question: if I have a polynomial-time NTM, can I build an equivalent polynomial-time DTM? | |
| Sep 25, 2008 at 4:44 | comment | added | Derek Park | As for needing the TM model, I honestly have as much trouble seeing how all non-deterministic TMs can computed on deterministic TMs as I do seeing how all polynomial-verification problem can be polynomial-computation problems. Both are hard for me to imagine being true. | |
| Sep 25, 2008 at 4:41 | comment | added | Derek Park | Well, my statement was unnecessarily harsh. The two expressions (yours and mine) of NP are apparently formally equivalent, so both are actually correct. I'd always heard P/NP expressed the way I described. | |
| Sep 24, 2008 at 18:26 | comment | added | Dima | Derek, correction. I think you did a nice job. Computed vs. verified makes a lot of sense. However, it is harder to see why something verified in P-time may ever be computed in P-time, without using the TM as a model. | |
| Sep 24, 2008 at 18:20 | comment | added | Dima | Derek, I beg to disagree. I really don't see how you explain P and NP without Turing machines. I was once in an algorithms class, which tried that. If I didn't know about TM's, I'd be totally lost. | |
| Sep 24, 2008 at 16:46 | comment | added | Derek Park | Okay, you made this way more complicated by bringing in non-deterministic Turing machines. That's totally a peripheral issue. | |
| Sep 24, 2008 at 16:40 | comment | added | Doug McClean | It isn't true that the only way to solve SAT is enumeration of cases. See en.wikipedia.org/wiki/… for info on the DPLL algorithm, which is actually very efficient in many common cases. | |
| Sep 24, 2008 at 15:24 | vote | accept | raldi | ||
| Sep 24, 2008 at 15:20 | history | answered | Dima | CC BY-SA 2.5 |