<p>Given an instance of 3SAT with $m$ clauses, you can find the set of clauses that are not satisfied in some optimal assignment with $O(m)$ calls to the oracle. </p>

<p>The algorithm: Call the oracle on the original input to find $k^*$, the maximum number of clauses that can be satisfied. For each clause, try removing the clause and then call the oracle. If the maximum number of clauses that can be satisfied is still $k^*$, then leave the clause removed. Otherwise, put the clause back in.</p>

<p>To prove the correctness of this algorithm, we make two observations.</p>

<p>Observation 1: Throughout the algorithm, the non-removed clauses are always a superset of the satisfied clauses of some optimal assignment. (To see this, proceed by contrapositive. Suppose that the non-removed clauses are not a superset of the satisfied clauses of any optimal assignment. Then we cannot satisfy $k^*$ of the non-removed clauses simultaneously, or else those $k^*$ clauses would be the clauses of an optimal assignment for which the non-removed clauses are a superset.)</p>

<p>Observation 2: The algorithm will end with $k^*$ non-removed clauses. (Suppose that we have strictly more than $k^*$ clauses. By Observation 1, there is some optimal assignment whose satisfied clauses are a subset of the non-removed clauses. Then we can remove the clauses that aren't satisfied by this optimal assignment and still have $k^*$ satisfied clauses, and these clauses would have been removed when the algorithm looped over the clauses.)</p>

<p>Combining these observations, we see that the non-remaining clauses are exactly the clauses satisfied by some optimal assignment. So then the clauses we removed would be the the desired not-satisfied clauses.</p>

CC BY-SA 3.0
2016-07-22T21:41:14.520Z
2016-07-22T21:41:14.520Z
Tom Tseng
<p>We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you the whether the maximum number of clauses you can satisfy when an equation is the input is $k$. Can you use a polynomial number of calls to the oracle to figure out the clauses that are <strong>not</strong> satisfied when provided an optimal assignment of the variables?</p>

<p>A simple statement that could help with this is that suppose you know the clauses that are not satisfied by an optimal assignment of variable values, then removing any subset of these clauses will <strong>not</strong> result in more clauses that can be satisfied. Is this statement true? </p>

CC BY-SA 3.0
2016-07-22T21:35:10.427Z
To clarify, are you looking for the clauses that aren't satisfied in *any* optimal assignment, or the clauses that aren't satisfied in *some* optimal assignment? (Also, yes, your statement is true.)
Tom Tseng
CC BY-SA 3.0
2016-07-23T15:34:31.463Z
Clauses that aren't satisfied in **some** optimal assignment.
user1246462
<np-hardness><approximation-algorithms><sat><approximation-hardness><oracles>
Given oracle for Max-3SAT compute clauses that cannot be satisfied
user1246462
# Given oracle for Max-3SAT compute clauses that cannot be satisfied

(Asked by: username_0 on 2016-07-22)

We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you the whether the maximum number of clauses you can satisfy when an equation is the input is $k$. Can you use a polynomial number of calls to the oracle to figure out the clauses that are **not** satisfied when provided an optimal assignment of the variables?

A simple statement that could help with this is that suppose you know the clauses that are not satisfied by an optimal assignment of variable values, then removing any subset of these clauses will **not** result in more clauses that can be satisfied. Is this statement true?

**Tags:** np-hardness, approximation-algorithms, sat, approximation-hardness, oracles
> **Comments:**
> **username_1**: To clarify, are you looking for the clauses that aren't satisfied in *any* optimal assignment, or the clauses that aren't satisfied in *some* optimal assignment? (Also, yes, your statement is true.)  
> **username_0**: Clauses that aren't satisfied in **some** optimal assignment.  

---

## 1 answers

### Answer by username_1 on 2016-07-22. Score: 3 | Accepted answer

Given an instance of 3SAT with $m$ clauses, you can find the set of clauses that are not satisfied in some optimal assignment with $O(m)$ calls to the oracle.

The algorithm: Call the oracle on the original input to find $k^\*$, the maximum number of clauses that can be satisfied. For each clause, try removing the clause and then call the oracle. If the maximum number of clauses that can be satisfied is still $k^\*$, then leave the clause removed. Otherwise, put the clause back in.

To prove the correctness of this algorithm, we make two observations.

Observation 1: Throughout the algorithm, the non-removed clauses are always a superset of the satisfied clauses of some optimal assignment. (To see this, proceed by contrapositive. Suppose that the non-removed clauses are not a superset of the satisfied clauses of any optimal assignment. Then we cannot satisfy $k^\*$ of the non-removed clauses simultaneously, or else those $k^\*$ clauses would be the clauses of an optimal assignment for which the non-removed clauses are a superset.)

Observation 2: The algorithm will end with $k^\*$ non-removed clauses. (Suppose that we have strictly more than $k^\*$ clauses. By Observation 1, there is some optimal assignment whose satisfied clauses are a subset of the non-removed clauses. Then we can remove the clauses that aren't satisfied by this optimal assignment and still have $k^\*$ satisfied clauses, and these clauses would have been removed when the algorithm looped over the clauses.)

Combining these observations, we see that the non-remaining clauses are exactly the clauses satisfied by some optimal assignment. So then the clauses we removed would be the the desired not-satisfied clauses.


---

