<p>Consider the decision problem:</p>
<p><strong>MIN-EQ-CNF</strong>= <span class="math-container">$\{\langle\phi, k\rangle |\exists \text{CNF formula } \psi \text{ of size }\leq k\text{ that is equivalent to the CNF formula }\phi\}$</span></p>
<p>CNF is a Boolean formula that is an AND of ORs and we say that two formulas are equivalent if they agree on all possible assignments. This problem is complete for the second level of polynomial hierarchy <span class="math-container">${\Sigma^P_2}$</span>.</p>
<p>Now lets consider a similar problem:</p>
<p><strong>MIN-EQ-3-CNF</strong>= <span class="math-container">$\{\langle\phi' , k\rangle | \exists \text{3-CNF formula } \psi' \text{of size }\leq k\text{ that is equivalent to the CNF formula } \phi'\}$</span>. In other words, given a 3SAT instance <span class="math-container">$\phi'$</span>, is there a 3SAT formula <span class="math-container">$\psi'$</span> of size <span class="math-container">$\leq k$</span> that is equivalent to <span class="math-container">$\phi'$</span>?</p>
<p><strong>Query:</strong> What is the computational complexity of this restricted MIN-EQ-3-CNF?</p>
<p><strong>Note:</strong> I am unclear how the size is defined in MIN-EQ-CNF. Thus, I am assuming the size of the formula is the number of clauses in MIN-EQ-CNF. Please correct this is incorrect. Similarly, in MIN-EQ-3-CNF we define the size as the number of clauses in the formula.</p>

CC BY-SA 4.0
2021-10-25T18:55:02.953Z
Thank you. I understand. The limitation of 3 literals per clause is what is bothering me. Is the restricted problem still complete for ${\Sigma^P_2}$ or is it simpler? Most texts talk about the general version.
J.Doe
CC BY-SA 4.0
2021-10-25T18:59:32.497Z
and what is the formal definition of size: number of clauses or something else?
J.Doe
CC BY-SA 4.0
2021-10-26T03:39:13.513Z
A small observation: in P^(NP) we can find a 3cnf G with a maximum number of clauses equivalent to a given F, if any 3cnf is equivalent to F: for each of the O(n^3) possible clauses C, if F is equivalent to (F AND C) then add C to G. This takes O(n^3) calls to SAT (in fact we could ask the queries in parallel). This adds every 3cnf clause consistent with F. (We could test with one more SAT query if F is equivalent to G.) Another consequence is it "suffices" to solve: given a 3cnf G, find a minimum subset of clauses G' equivalent to G. If this is in P^NP then the original problem is in P^NP...
Ryan Williams
<cc.complexity-theory><polynomial-hierarchy>
Computational Complexity of MIN-EQ-3-CNF
J.Doe
# Computational Complexity of MIN-EQ-3-CNF

(Asked by: username_0 on 2021-10-25)

Consider the decision problem:

**MIN-EQ-CNF**= $\{\langle\phi, k\rangle |\exists \text{CNF formula } \psi \text{ of size }\leq k\text{ that is equivalent to the CNF formula }\phi\}$

CNF is a Boolean formula that is an AND of ORs and we say that two formulas are equivalent if they agree on all possible assignments. This problem is complete for the second level of polynomial hierarchy ${\Sigma^P\_2}$.

Now lets consider a similar problem:

**MIN-EQ-3-CNF**= $\{\langle\phi' , k\rangle | \exists \text{3-CNF formula } \psi' \text{of size }\leq k\text{ that is equivalent to the CNF formula } \phi'\}$. In other words, given a 3SAT instance $\phi'$, is there a 3SAT formula $\psi'$ of size $\leq k$ that is equivalent to $\phi'$?

**Query:** What is the computational complexity of this restricted MIN-EQ-3-CNF?

**Note:** I am unclear how the size is defined in MIN-EQ-CNF. Thus, I am assuming the size of the formula is the number of clauses in MIN-EQ-CNF. Please correct this is incorrect. Similarly, in MIN-EQ-3-CNF we define the size as the number of clauses in the formula.

**Tags:** cc.complexity-theory, polynomial-hierarchy
> **Comments:**
> **username_0**: Thank you. I understand. The limitation of 3 literals per clause is what is bothering me. Is the restricted problem still complete for ${\Sigma^P_2}$ or is it simpler? Most texts talk about the general version.  
> **username_0**: and what is the formal definition of size: number of clauses or something else?  
> **username_1**: A small observation: in P^(NP) we can find a 3cnf G with a maximum number of clauses equivalent to a given F, if any 3cnf is equivalent to F: for each of the O(n^3) possible clauses C, if F is equivalent to (F AND C) then add C to G. This takes O(n^3) calls to SAT (in fact we could ask the queries in parallel). This adds every 3cnf clause consistent with F. (We could test with one more SAT query if F is equivalent to G.) Another consequence is it "suffices" to solve: given a 3cnf G, find a minimum subset of clauses G' equivalent to G. If this is in P^NP then the original problem is in P^NP...  

---

## 0 answers

