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

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)$.

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$). 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.

StackExchange Computer Science Q#19582, answer score: 7