3
$\begingroup$

Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals.

For every assignment of the variables which satisfies the system, one may consider the set of variables equal to true : these form a subposet of the poset of all variables.

QA) I would like to know the complexity (NP-complete, #P-complete etc.) of the following problems: find a satisfying assignment of the variables such that the set of variables to true is

  1. minimal with respect to inclusion
  2. of minimum cardinal among all solutions

QB) Can one construct such a system with both several inclusion-minimal solutions of non minimal cardinal and several cardinal-minimal solutions?

I am especially interested in those systems with the following "planarity / connectedness restrictions": the variables are the vertices of a planar graph whose faces have degree 4 and the variables in any clause must form a connected subgraph.

What do questions A and B become in this context?

PS : I am rather new to these satisfiability questions, I consulted a few references online (relevant Wikipédia pages, the "Handbook of satisfiability", courses etc) without seeing any mention of this question. There are some papers about "MIN-SAT" and "MAX-SAT" but these address a different question, namely extremize the number of satisfied clauses, whereas i'm interested in extremizing the number of variables.

Thanks you for your help,

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ For QA.2 see this CS stack exchange question. For QA.1 there's a simple linear algorithm: start with all variables set to 1, go over them in some order, and if they can be set to 0 while still satisfying the formula do that. $\endgroup$
    – Daniel Weber
    Commented Jan 19 at 3:41
  • $\begingroup$ @CommandMaster I don't see how the simple linear algorithm achieves minimum cardinality. For example, if the system is $(x_1 \vee x_2) \wedge (x_1 \vee x_3)$, and you start by setting $x_1$ to $0$, you get the solution $(0,1,1)$ rather than the minimum $(1,0,0)$. $\endgroup$
    – Robert Israel
    Commented Jan 19 at 4:36
  • 3
    $\begingroup$ @RobertIsrael it doesn't, it gives a set minimal with respect to inclusion. The CS SE question I linked shows that minimum cardinality is NP-hard $\endgroup$
    – Daniel Weber
    Commented Jan 19 at 5:25
  • 1
    $\begingroup$ Vertex cover in graph and "one in three sat" are examples for NP-hardness. $\endgroup$
    – joro
    Commented Jan 19 at 10:38
  • $\begingroup$ @CommandMaster Thank you for the links, this is a good start. Indeed, inclusion minimal is easy to find, but for this question i wish to know the number of minimal solutions : given k, are there more than k inclusion-minimal solutions ? I'm am actually much more interested in the cardinal-minimal question: given k, is there a solution with < k variables set to true. According to the answers of the CS question, it is equivalent to the vertex cover set problem, which is NP hard even for planar graphs, and multigraphs. That answers QB, and hints towards my "plane-connected" conditions. $\endgroup$
    – Christopher-Lloyd Simon
    Commented Jan 21 at 2:36

0

Reset to default

You must log in to answer this question.