2
$\begingroup$

Since the P vs. NP problem is still an open problem, 2-SAT and Clique might both be in P if P = NP. Is there any known complexity measure whatsoever that is already mathematically proven to distinguish 2-SAT from Clique?

$\endgroup$

2 Answers 2

8
$\begingroup$

2-SAT is NL-complete so separating 2-SAT from Clique would separate NP from NL, also a major open problem.

$\endgroup$
1
  • $\begingroup$ Many thanks, Lance!! $\endgroup$
    – ShyPerson
    Jan 20 at 0:43
5
$\begingroup$

I think there is at least one model of computation where 2-SAT is easy and Clique is provably hard: resolution refutation complexity (i.e. how hard is to deduce contradiction from the initial clauses using resolution inference rule). If you think about decision problem instead of refutation, you may ask "how hard is for a Resolution based SAT-solver to solve 2-SAT, and what about Clique?".

Of course in this case you have to take in account a specific encoding of Clique as a CNF formula.

This is a very specific model of computation, but covers algorithms that are quit common in practice (well, more common than bounded-depth circuit I would say).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.