<p><strong>MCS problem:</strong> Given a set $\phi$ of Boolean clauses. Find a minimal correction subset (MCS) $M\subseteq\phi$ such that: $\phi\setminus M$ is satisfiable and for all $c\in M$ holds $\phi\setminus (M\setminus\{c\})$ is unsatisfiable.</p>

<p>I would like to know the complexity hardness of this problem, but I just could not find a clear answer to this question:</p>

<p><strong>Is the computation of a minimal correction subset (MCS) $FP^{NP}$-hard?</strong></p>

<p>A similiar question would be '<strong>Is the computation of a maximal satisfiable subset (MSS) $FP^{NP}$-hard?</strong>', since the complement of an MCS is an MSS.</p>

<p>Obviously, the MCS/MSS problem is in the class $FP^{NP}$, since we can iterate over all clauses and check for satisfiability. If satisfiable, add clause to the MSS, otherwise add clause to the MCS.  See for example <a href="http://ijcai.org/papers13/Papers/IJCAI13-098.pdf">[Marques-Silva, On Computing Minimal Correction Subsets, 2013]</a></p>

<p>If this question is an open research topic, I would be happy, if someone could confirm it (and possibly give a reference to a recent paper).</p>

<hr>

<p>I just found a paper <a href="http://eccc.hpi-web.de/report/2014/031/">'On the Query Complexity of Selecting Few Minimal Sets'</a> by Marques-Silva and Janota (2014). In the introduction it states:
"For example, it is not known what is the best worst-case number of calls to a SAT solver for computing [..] <strong>a maximally satisable subset</strong> [..]".</p>

<p>Unfortunately, the paper shows no further references to underline this statement. But, if I interpret '<em>best worst-case</em>' correctly, it says that there is no known hardness result for MSS (and therefore for MCS, too) in terms of SAT solver calls. Anyone agree or disagree? </p>

CC BY-SA 3.0
2015-05-09T17:15:29.777Z
are you talking about this [FP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fp)? a (re)statement of the problem without this somewhat obscure complexity class might help, & the other basic defns of the terms etc
vzn
CC BY-SA 3.0
2015-05-09T17:44:46.330Z
its not really stated here as a decision problem. the decision problem is Y/N. a decision problem might be (eg) given a SAT formula & set of clauses, is the latter an MCS or an MSS. but then isnt this easy to verify? (so actually not sure how to model this as a decision problem that captures its complexity.) note (from a paper) "MSS is a generalization of well-known MaxSAT" so an analysis might link them. MaxSAT measures cardinality (vs given threshhold) of the subset of satisfiable clauses.
vzn
CC BY-SA 3.0
2015-05-09T18:02:36.810Z
there seem to be some results/ study on the closely related MUS, minimal unsatisfiable subset, but not sure yet of its precise interrelation to MCS/MSS... oh, see you maybe intentionally dont want the decision problem. think this is nearly a [cstheory.se] question....
vzn
CC BY-SA 3.0
2015-05-09T21:10:01.843Z
@vzn Thank you for your comments and hints. As you already mentioned, MUS and MCS/MSS are closely related (known as dual hitting set property). As far as I know, the complexity hardness of a MUS is also an open research topic. MaxSAT concerns of MSS with maximum cardinality, whereas MSS only concerns about maximal (w.r.t . set inclusion). Yes, I mean FP and not the corresponding decision problem of verifying if a given set is a MCS/MSS. I am interested in the problem of finding any MCS (if one exists).
John Threepwood
CC BY-SA 3.0
2015-05-10T18:52:24.460Z
found that update2 paper wrt query complexity by Marques-Silva also when writing my prior comment about MUS. there is a ref to its complexity as an open problem p6.... it appears all these related problems are "mostly open" wrt "nontrivial" complexity classifications... they cite [5] chen/ toda 1995 for MUS complexity where maybe slightly more is known in the literature. again suggest ask on [cstheory.se]. yes the dual hitting set property, relatively recently uncovered, seems also key in classifying complexity & has some implications which maybe havent been worked out in detail yet.
vzn
CC BY-SA 3.0
2015-05-10T19:01:02.960Z
@vzn Thanks again for your hints. I flagged the question for migration to Theoretical Computer Science.
John Threepwood
CC BY-SA 3.0
2015-09-27T22:17:31.583Z
FP^NP seems to me to be a pretty poorly understood complexity class. All the known FP^NP-complete problems appear to be weighted (like TSP, knapsack, weighted max-cut), but never purely combinatorial. The complexity status of finding a maximum clique doesn't even appear to be known, and the only "natual" answer would seem to be FP^NP-complete. So I don't see any good problems to reduce from. Relevant paper: http://www.sciencedirect.com/science/article/pii/0022000088900396
Dominik Peters
<cc.complexity-theory><sat>
Is the computation of a minimal correction subset (MCS) $FP^{NP}$-hard?
John Threepwood
# Is the computation of a minimal correction subset (MCS) $FP^{NP}$-hard?

(Asked by: username_0 on 2015-05-07)

**MCS problem:** Given a set $\phi$ of Boolean clauses. Find a minimal correction subset (MCS) $M\subseteq\phi$ such that: $\phi\setminus M$ is satisfiable and for all $c\in M$ holds $\phi\setminus (M\setminus\{c\})$ is unsatisfiable.

I would like to know the complexity hardness of this problem, but I just could not find a clear answer to this question:

**Is the computation of a minimal correction subset (MCS) $FP^{NP}$-hard?**

A similiar question would be '**Is the computation of a maximal satisfiable subset (MSS) $FP^{NP}$-hard?**', since the complement of an MCS is an MSS.

Obviously, the MCS/MSS problem is in the class $FP^{NP}$, since we can iterate over all clauses and check for satisfiability. If satisfiable, add clause to the MSS, otherwise add clause to the MCS. See for example [[Marques-Silva, On Computing Minimal Correction Subsets, 2013]](http://ijcai.org/papers13/Papers/IJCAI13-098.pdf)

If this question is an open research topic, I would be happy, if someone could confirm it (and possibly give a reference to a recent paper).

---

I just found a paper ['On the Query Complexity of Selecting Few Minimal Sets'](http://eccc.hpi-web.de/report/2014/031/) by Marques-Silva and Janota (2014). In the introduction it states:
"For example, it is not known what is the best worst-case number of calls to a SAT solver for computing [..] **a maximally satisable subset** [..]".

Unfortunately, the paper shows no further references to underline this statement. But, if I interpret '*best worst-case*' correctly, it says that there is no known hardness result for MSS (and therefore for MCS, too) in terms of SAT solver calls. Anyone agree or disagree?

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_1**: are you talking about this [FP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fp)? a (re)statement of the problem without this somewhat obscure complexity class might help, & the other basic defns of the terms etc  
> **username_1**: its not really stated here as a decision problem. the decision problem is Y/N. a decision problem might be (eg) given a SAT formula & set of clauses, is the latter an MCS or an MSS. but then isnt this easy to verify? (so actually not sure how to model this as a decision problem that captures its complexity.) note (from a paper) "MSS is a generalization of well-known MaxSAT" so an analysis might link them. MaxSAT measures cardinality (vs given threshhold) of the subset of satisfiable clauses.  
> **username_1**: there seem to be some results/ study on the closely related MUS, minimal unsatisfiable subset, but not sure yet of its precise interrelation to MCS/MSS... oh, see you maybe intentionally dont want the decision problem. think this is nearly a [cstheory.se] question....  
> **username_0**: @username_1 Thank you for your comments and hints. As you already mentioned, MUS and MCS/MSS are closely related (known as dual hitting set property). As far as I know, the complexity hardness of a MUS is also an open research topic. MaxSAT concerns of MSS with maximum cardinality, whereas MSS only concerns about maximal (w.r.t . set inclusion). Yes, I mean FP and not the corresponding decision problem of verifying if a given set is a MCS/MSS. I am interested in the problem of finding any MCS (if one exists).  
> **username_1**: found that update2 paper wrt query complexity by Marques-Silva also when writing my prior comment about MUS. there is a ref to its complexity as an open problem p6.... it appears all these related problems are "mostly open" wrt "nontrivial" complexity classifications... they cite [5] chen/ toda 1995 for MUS complexity where maybe slightly more is known in the literature. again suggest ask on [cstheory.se]. yes the dual hitting set property, relatively recently uncovered, seems also key in classifying complexity & has some implications which maybe havent been worked out in detail yet.  
> **username_0**: @username_1 Thanks again for your hints. I flagged the question for migration to Theoretical Computer Science.  
> **username_2**: FP^NP seems to me to be a pretty poorly understood complexity class. All the known FP^NP-complete problems appear to be weighted (like TSP, knapsack, weighted max-cut), but never purely combinatorial. The complexity status of finding a maximum clique doesn't even appear to be known, and the only "natual" answer would seem to be FP^NP-complete. So I don't see any good problems to reduce from. Relevant paper: http://www.sciencedirect.com/science/article/pii/0022000088900396  

---

## 0 answers

