-1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Tom Tseng Jul 22 '16 at 21:35
  • $\begingroup$ Clauses that aren't satisfied in some optimal assignment. $\endgroup$ – user1246462 Jul 23 '16 at 15:34
  • $\begingroup$ In that case, do you mean [the set S given by [C is in S if and only if there is an optimal assignment that does not satisfy C]] or ["the" set S such that there exists an optimal assignment A such that S is given by [C is in S if and only if A does not satisfy C]]? ​ ​ $\endgroup$ – user6973 Jul 23 '16 at 20:11
  • $\begingroup$ The scare quotes are because there can easily be more than one "set S such that ... does not satisfy C]" - Consider the 3-variable 8-clause instances in which each variable occurs exactly once in each clause and the 8 sets of literals are all distinct. ​ If that's what you mean, then how should S be chosen? ​ (For example, are you really just after a "set S such that ... does not satisfy C]", which the algorithm can choose, rather than the "set S such that ... does not satisfy C]", specified in some unknown-to-me way?) ​ ​ ​ ​ $\endgroup$ – user6973 Jul 23 '16 at 20:11
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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