Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Can we get a laymans explanation of what this is about? I understand what p np is, but don't really understand what this person is claiming. Is this some kind of claim about the overall concept of p np? Or proving a specific case?


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.


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.


This is a specific case that (maybe) proves the general claim that P != NP.

Proving an inequality is "easy", because only requires a single counterexample: if there is one problem in NP that is not in P (I.e. an NP problem not solvable in polynomial time), then NP can't possible equal P.

Fukuyama is proposing that CLIQUE is such a counter-example.

(Proving the inequality doesn't actually require the special property of NP-completeness which others are talking about; that is only useable in a proof P = NP.)


> Proving an inequality is "easy", because only requires a single counterexample:

Proving an equality isn't exactly "harder" (no NP-hard pun intended) - all you have to do is show that a single NP-complete problem can be reduced to a problem within P in polynomial time.


That's true in this case, but only because we have other results showing that various problems are NP-complete.


I think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.


The claim is that since clique is in NP-complete and not P, P != NP. (Every problem in P is in NP.)


Basically prove/disprove a p-np problem can be solved(in polynomial time) then you've proved it for the rest of the p-np problems.


I think that you mean a NP-complete problem. There's no such thing as a "p-np problem".




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: