Complexity of this variant of 3-SAT?

Question

This post introduces a new variant of 3-SAT called EQUAL-3-SAT, where the number of 3-Literal clause is equal to the number of variable.

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.

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)$, This is an instance of EQUAL -3-SAT.

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)$. This is not EQUAL-3-SAT Insatance.

By, EQUAL-3-SAT we mean a set of clause such that each clause can contain at most 3 -literal and at least 1 literal ,but the total number of clauses in this set of clause is same as the number of variables present and this restrcition on the number of clauses is applicable even on clauses with literals < 3.

I was curious if the following variant of EQUAL-3-SAT are NP-complete:

1. EQUAL-3-NAE-SAT where the number of clause is the still same as the number of number of variable but we need to check if its Not-all-Equal Satisfiable.

I thought the usual reduction from 3-SAT to 3-NAE-SAT would work here but I got confused as to how the reduction would work when there's a restriction on the number of clauses we can have with respect to the variables.

Is the above mentioned variant of EQUAL-3-SAT Np-Complete?

Answer 1

Yes. Given any formula with more clauses than variables, pad with extra clauses of the form

$$(x_t \lor x_u)$$

where $x_t,x_u$ are fresh new variables used only in that clause. You can verify that in this way you can add enough padding to meet the "EQUAL" requirement. You should be able to take it from here.