Timeline for Intuitive example of an NP problem
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2018 at 20:37 | comment | added | Draco18s no longer trusts SE | @YuvalFilmus Ah, I was thinking about it backwards. :) | |
| May 4, 2018 at 20:32 | comment | added | Yuval Filmus | @Draco18s Hint: $K_{3,3}$ is 2-colorable although it's not planar. | |
| May 4, 2018 at 20:30 | comment | added | Draco18s no longer trusts SE | @YuvalFilmus The four color theorem was proved in 1976. It was the first major theorem to be proved using a computer. If a graph can be shown to be planar in linear time, then it must also be 4-colorable, no? | |
| Jun 29, 2017 at 2:01 | comment | added | Yuval Filmus | I'm not sure what this example is supposed to show, but actually planarity can be tested in linear time, whereas testing whether a graph is 4-colorable is NP-complete. | |
| Jun 16, 2017 at 15:21 | comment | added | Ben I.♦ | That's a much more intuitive example. Thanks! | |
| Jun 16, 2017 at 14:57 | review | First posts | |||
| Jun 16, 2017 at 15:01 | |||||
| Jun 16, 2017 at 14:52 | history | answered | MTSan | CC BY-SA 3.0 |