2
$\begingroup$

I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case?

I tried reducing 3-SAT to it by expanding, but this introduces $2^{k-3}$ extra clauses per original 3-SAT clause, hence the reduction is not polynomial when $k=n/2$. Any ideas?

$\endgroup$
3
  • 1
    $\begingroup$ Can you share the context where you encountered this question? Can you credit the source? $\endgroup$
    – D.W. ♦
    Jan 9, 2021 at 8:49
  • $\begingroup$ I suggest you work on how to reduce 3SAT to 4SAT (where every clause has exactly 4 variables). $\endgroup$
    – D.W. ♦
    Jan 9, 2021 at 8:50
  • $\begingroup$ I'm the source.. :-) 3-SAT to 4-SAT is easy. For each clause c just expand it to (c+v)(c+v'), where v is a new variable. This also works for any constant k like 5SAT, 6SAT, etc... But the method breaks down when k >> logn, like in this case where k=n/2 (I also pointed to this in my initial post). $\endgroup$
    – dda
    Jan 9, 2021 at 10:01

1 Answer 1

Reset to default
1
$\begingroup$

Your problem is actually in P. First of all, you can assume that no clause contains both a variable and its negation, since such clauses are always satisfied. Suppose that the instance contains $m$ clauses. Then a random assignment will falsify your formula with probability $m/2^{n/2}$. If $m < 2^{n/2}$, then this means that your formula is satisfiable. Otherwise, the input is of size at least $2^{n/2}$, and so you can go over all $2^n$ truth assignments in polynomial time.

$\endgroup$
4
  • $\begingroup$ By the same argument, doesn't that mean that for any $k=\omega(logn)$, k-SAT is P? $\endgroup$
    – dda
    Jan 9, 2021 at 13:37
  • $\begingroup$ Not quite. You need $k$ to be linear in $n$. This gap is where ETH should come in. $\endgroup$
    – Yuval Filmus
    Jan 9, 2021 at 14:56
  • $\begingroup$ ETH?? Anyway, I was referring to the fact that if the number of clauses is poly(n) and $k=\omega(logn)$, then by the first part of your argument the formula is satisfiable... To rephrase the original post, for which values of k (other than the usual k=3,4,..), the problem is NP-complete? Any pointers/ideas? Thanks again! $\endgroup$
    – dda
    Jan 9, 2021 at 16:32
  • $\begingroup$ Exponential time hypothesis. The first part of my argument depends on their being relatively few clauses. $\endgroup$
    – Yuval Filmus
    Jan 9, 2021 at 16:33

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.