Timeline for Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

12 events

when toggle format	what		by	license	comment
Dec 12, 2014 at 18:01	comment	added	Mark Dominus		In Proof that SAT is NPC I explained in detail why a polynomial-time solution to SAT would provide a polynomial-time solution for any other problem in NP, such as 3-coloring.
Dec 12, 2014 at 11:14	vote	accept	Mill
Dec 12, 2014 at 11:12	history	tweeted			twitter.com/#!/StackCompSci/status/543362854783844352
Dec 12, 2014 at 10:48	history	edited	Mill	CC BY-SA 3.0	edited body
Dec 12, 2014 at 10:48	answer	added	David Richerby		timeline score: 2
Dec 12, 2014 at 10:46	answer	added	Tom van der Zanden		timeline score: 5
Dec 12, 2014 at 10:11	history	edited	Mill	CC BY-SA 3.0	added 354 characters in body
Dec 12, 2014 at 10:04	history	edited	David Richerby		edited tags
Dec 12, 2014 at 9:54	answer	added	JiK		timeline score: 1
Dec 12, 2014 at 9:51	history	edited	Mill	CC BY-SA 3.0	added 2 characters in body
Dec 12, 2014 at 9:35	review	First posts
Dec 12, 2014 at 9:48
Dec 12, 2014 at 9:34	history	asked	Mill	CC BY-SA 3.0