$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?
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 &lt; 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.