# Computational Complexity of an 'equivalent' 3SAT instance problem

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

Objective: For any given value $$C_1$$ ($$C_1), 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?

• 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. Oct 25, 2021 at 10:58
• 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.." Oct 25, 2021 at 11:13
• You never stated that the sought equivalent 3SAT instance must have $C_1$ clauses. Oct 25, 2021 at 11:14
• a mistake, making an edit. apologies. Oct 25, 2021 at 11:17

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.
• 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. Oct 25, 2021 at 12:01