Timeline for What are the most important results (and papers) in complexity theory that every one should know?
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2010 at 20:37 | comment | added | Sridhar Ramesh | The mere fact that NP-complete problems exist is (or should be) obvious and immediate once one has the insight to consider the concept in the first place: the problem "Given a nondeterministic machine P, and a number N in unary, determine if it is possible for P to halt in N steps" is clearly NP-complete. The fact that so many other naturally arising problems turn out to be NP-complete is what makes it interesting. | |
| Aug 4, 2010 at 12:48 | history | edited | Antonio E. Porreca | CC BY-SA 2.5 |
deleted 2 characters in body
|
| Aug 4, 2010 at 9:33 | history | edited | Stefan Geschke | CC BY-SA 2.5 |
Explained the theorems.
|
| Aug 4, 2010 at 9:22 | history | answered | Stefan Geschke | CC BY-SA 2.5 |