# $k$-SAT completeness proof when $k$ is linear in number of variables

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?

• Can you share the context where you encountered this question? Can you credit the source?
– D.W.
Jan 9 at 8:49
• I suggest you work on how to reduce 3SAT to 4SAT (where every clause has exactly 4 variables).
– D.W.
Jan 9 at 8:50
• 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).
– dda
Jan 9 at 10:01

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.
• By the same argument, doesn't that mean that for any $k=\omega(logn)$, k-SAT is P?
• Not quite. You need $k$ to be linear in $n$. This gap is where ETH should come in. Jan 9 at 14:56
• 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!