4 ms·
I wish I had the mathematical background to comprehend this. It's very involved. My understanding is that he has shown that CLIQUE (a known NP-complete problem)
by gburt 14y ago
I wish I had the mathematical background to comprehend this. It's very involved. My understanding is that he has shown that CLIQUE (a known NP-complete problem) takes exponential time and thus is not solvable in polytime, this would mean there is a problem outside of P but inside of NP, and this P != NP.
- GoGoGalois 14y agoIf a problem is NP complete then there is an algorithm to solve it in nondeterminstic polynomial time. Any nondet algorithm can be transformed to an exp poly time algorithm (just run through each of your poly time algorithms one by one) so showing CLIQUE has an exp algorithm doesn't help at all. We want a lower bound.
- morsch 14y agoYes, that's what he is saying, every CLIQUE algorithm takes at least exponential time.
- GoGoGalois 14y agoOh ok, I thought the first post was referring to a single algorithm, not every possible algorithm. My mistake.
- gburt 14y agoSorry, if I could I would edit it to be more clear. We definitely need to show that no algorithm can exist with poly runtime for all inputs.
- mdxn 14y agoNo, he is claiming that l-CLIQUE requires exponential circuit size (this is the reason that most of the proof talks about circuit complexity and not time bounded Turing Machines). This is not necessarily the same thing as exponential time.