Timeline for Good examples of "two is easy, three is hard" in computational sciences
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 20, 2019 at 3:00 | comment | added | GoHokies | @findusl You’re perfectly right. What makes 3-SAT and 3-coloring “special” is the 2-vs-3 dichotomy of the OP. | |
| May 16, 2019 at 16:47 | comment | added | findusl | @GoHokies I thought that is true for every np-complete problem? Or is something especially noteworthy about these two? Sry if this is a stupid question, my knowledge on this area is basic. But this is how I understand cooks theorem | |
| May 16, 2019 at 9:38 | comment | added | GoHokies | 3-SAT can be reduced to graph 3-coloring, or vice-versa | |
| May 16, 2019 at 9:20 | history | answered | Federico Poloni | CC BY-SA 4.0 |