Hacker News Reader

If I understand it right he showed that Clique cannot be solved in polynomial time, since any NP complete problem is at least as hard as Clique none of those problems can be solved in polynomial time. So he used Clique to draw general conclusion that P!=NP.

View on HN

This only works if all NPC problems can be converted to CLIQUE?

All NP problems can be converted into the other NP problems, therefore if you can prove it for one NP problem, you prove it for all NP problems.

You missed a few words. Any NP-complete problem can be converted into any other NP-complete problem in polynomial time.

Right, oops.

Reply on news.ycombinator.com