4
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
-4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Assuming that $\mathrm{P\neq NP}$, your answer directly contradicts the other answer, but you provide no evidence for your claim. $\endgroup$ – David Richerby Feb 4 at 15:35
  • 3
    $\begingroup$ We're looking for answers that come with evidence, justification, proof or other explanation. If you can provide that, I encourage you to edit your answer to elaborate. Thank you! $\endgroup$ – D.W. Feb 4 at 16:50
  • $\begingroup$ Ok, I will show my algorithm for case n = m. We can present SAT problem as bipartite graph en.wikipedia.org/wiki/Bipartite_graph . If we use notation from Wikipedia, then we can say that vertices from set U are variables and vertices from set V are clauses. We put edge from U to V when proper variable appears in proper clause (not important if positive or negation). If number of variables is the same as number of clauses, then we only have to find one perfect matching. This will not work in case presented by Juho, so case n = m is not in P, but it will work in many practical cases. $\endgroup$ – user99964 Feb 17 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.