2
$\begingroup$

I'm trying to solve a problem which I can solve in 3SAT or as a mixed 2,3,4 SAT. I know how hard each of those categories are individually and know the derivations of their hardness individually. But I don't see how those can be combined to give me an idea of comparative hardness of 3SAT vs 2,3,4 SAT. By how hard, I mean what's the scaling with increasing numbers of variables.

$\endgroup$
1
  • 1
    $\begingroup$ As soon as you allow an arbitrary number of clauses with $3$ or more literals the problem becomes $\mathsf{NP}$-hard. For any fixed number of clauses with $3$ or more variables the problem is still in $\mathsf{P}$. In fact, the problem is in $\mathsf{P}$ even if the above clauses are at most $c \log n$ for some constant $c$, where $n$ is the number of variables. $\endgroup$
    – Steven
    Jul 13, 2022 at 10:28

1 Answer 1

1
$\begingroup$

I think Steven's comment answers this sufficiently: 2SAT is in P, anything above that is NP-hard. By mixing it I just have two different NP-hard problems. How exactly 3SAT and 2,3,4 SAT differ in scaling probably depends on my algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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