0
$\begingroup$

Is there any known complexity measure whatsoever that can distinguish 2-SAT from Clique?

$\endgroup$
2
  • 2
    $\begingroup$ One is in P and the other is NP-hard. $\endgroup$ Jan 5 at 7:04
  • $\begingroup$ @YuvalFilmus: If P = NP, then 2-SAT and Clique are both in P. Or am I missing something? $\endgroup$
    – ShyPerson
    Jan 14 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.