4 ms·
I think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.
by nate_martin 14y ago
I think he is showing the clique problem cannot be solved in polynomial time. Since clique is in NP and not P, P!=NP.
- cgray4 14y agoThe claim is that since clique is in NP-complete and not P, P != NP. (Every problem in P is in NP.)