Given a random $3SAT$ instance $(S_0)$ with $C_0$ clauses, $I_0$ variables.

Objective: For any given value $C_1$ ($C_1<C_0$), create an 'equivalent' $3SAT$ instance $(S_1)$ with $I_0$ variables, $C_1$ clauses such that:
For any set of values for variables $I_0$, $S_0$ is satisfiable iff $S_1$ is satisfiable.

What is the computational complexity of this problem? It doesn't seem to be $NPComplete$ since there is no obvious way to verify the equivalence of two instances $S_0$ and $S_1$. Or I am missing something? Any refernces please?

  • $\begingroup$ Since the objective does not seem to depend on $C_1$ in any way, what's preventing you from picking $S_1 = S_0$? Also the problem cannot possibly be $\mathsf{NP}$-complete since it is not a decision problem. $\endgroup$
    – Steven
    Oct 25, 2021 at 10:58
  • $\begingroup$ I think I might not have made it very clear. When we are given $C_1$ as a target as part of the problem statement how can we assume $S_1=S_0$. The whole point is to minimize the 3SAT instance? We can also translate it into a decision problem by stating "Is there an equivalent 3SAT instance for a given value $C_1$ so that shouldn't be a problem. I am curious about the complexity of both: 1. Finding the equivalent 3SAT 2. The decision version of the form "Is there an.." $\endgroup$
    – J.Doe
    Oct 25, 2021 at 11:13
  • $\begingroup$ You never stated that the sought equivalent 3SAT instance must have $C_1$ clauses. $\endgroup$
    – Steven
    Oct 25, 2021 at 11:14
  • $\begingroup$ a mistake, making an edit. apologies. $\endgroup$
    – J.Doe
    Oct 25, 2021 at 11:17

1 Answer 1


Suppose that your problem can be solved in polynomial time. Then you can obtain an algorithm that solves 3SAT as follows.

Given an instance $\phi$ of 3SAT with $n \ge 3$ variables and $m \ge 9$ clauses, invoke a polynomial-time algorithm for your problem with $C_1=8$.

If your algorithm answers with a formula $\phi'$, then you can test at most $2^{24}$ instantiations of the (at most) $24$ variables involved in the $8$ clauses of $\phi'$ to decide whether $\phi$ is satisfiable.

If your algorithm determines that no such formula $\phi'$ exists, then $\phi$ is necessarily satisfiable since you can always build a non-satisfiable 3SAT formula if you are allowed to use at least $3$ variables and $8$ clauses.

  • $\begingroup$ Isn't it possible that the minimum equivalent problem instance might have a size $C_1>8$. How does that say anything about satisfiablility or unsatisfiability of the original problem? I am very confused. $\endgroup$
    – J.Doe
    Oct 25, 2021 at 12:01
  • $\begingroup$ If the minimum equivalent instance has more than 8 clauses then the original 3-SAT instance must be satisfiable. $\endgroup$
    – Steven
    Oct 25, 2021 at 12:21
  • $\begingroup$ I understood that assertion but I could not see the reasoning how hence the confusion. Moreover, I was searching for some equivalent problem and I stumbled on the MIN-EQ-DNF problem. That belongs to the second level in the Polynomial Hierarchy. Our problem is similar but has 2 differences: 1. Each clause is in CNF 2. Each clause has a fixed/exact size of 3 unlike the MIN-EQ-DNF problem. I was wondering if they are related? Here is the link: theory.epfl.ch/courses/complexity/Lecture6.pdf $\endgroup$
    – J.Doe
    Oct 25, 2021 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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