0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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$ Commented 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$ Commented Oct 25, 2021 at 11:13
  • $\begingroup$ You never stated that the sought equivalent 3SAT instance must have $C_1$ clauses. $\endgroup$ Commented Oct 25, 2021 at 11:14
  • $\begingroup$ a mistake, making an edit. apologies. $\endgroup$ Commented Oct 25, 2021 at 11:17

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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$ Commented 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$ Commented 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$ Commented 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.