3-SAT problem with number of clauses equal to number of variables

Question

Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is this problem still NP-hard?

For example, this formula has $3$ variables and has $3$ clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3 ) \wedge (\lnot x_1 \vee \lnot x_3) \wedge (\lnot x_2 \vee \lnot x_3)$,

and the following formula has three variables but has only two clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3 ) \wedge (\lnot x_2 \vee \lnot x_3)$.

Answer 1

Let the variant of the 3-SAT problem you describe be called EQUAL-3-SAT, where (following your definition) each clause has at most 3 literals. We prove EQUAL-3-SAT is NP-complete by a reduction from 3-SAT as follows.

Let $\phi$ be an instance of 3-SAT with $n$ variables and $m$ clauses. If $\phi$ is balanced already in the beginning (the case $n=m$), we do nothing. If $n > m$, we introduce a fresh variable $x$ that does not appear anywhere in $\phi$ and add to $\phi$ exactly $n-m+1$ clauses of the form $(x)$, so we have $n=m$, and we are done.

Then, if $n < m$, we can do similar balancing: each addition of a 3-literal clause $(a \vee b \vee c)$, where $a$, $b$ and $c$ are fresh variables, increases $n$ by $3$, and $m$ by $1$. Keep adding this clause to $\phi$ until $n=m$, or the difference between $n$ and $m$ is exactly one or three (if the difference was two, repeating the process once more would balance $\phi$). If the difference is one, adding one more 3-literal clause causes $n=m+1$ thus we use the balancing process of the first step (case $n > m$). If the difference is three, we simply add an 2-clause of the form $(a \vee b)$, increasing $n$ by two and $m$ by one, again giving us $n=m$.

Finally, we observe the new formula is satisfiable if and only if $\phi$ was.

Answer 2

If number of clauses is equal to number of variables this problem is in P.