I am very interested in the following questions, which sprang out from the topological study of loops in surfaces and their intersection numbers.

Consider, over a finite set of boolean variables $X$, a Boolean formula in CNF (conjunctive normal form) whose clauses only contain non-negated literals.
Assume 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 induce a connected subgraph.

For every assignment $a$ of the variables which satisfies the formula, one may consider the following subset of $X$: $T_a = \{x\in X: a(x) \mathrm{\:is\:true}\}$.
A satisfying assignment $a$ will thus be called minimal if $T_a$ is minimal with respect to inclusion and optimal if $T_a$ has minimal cardinality among all solutions.

QA) What is the complexity (NP-complete, P-space-complete, etc.) of the following problems ?

  1. Compute the size $|T_a|$ of optimal solutions.
  2. Construct an optimal solution.

QB) For which positive integers $m \le M$ can one construct such a formula with $m$ optimal solutions and $M$ minimal solutions?

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.

PPS: According to this cs.stackexchange thread, my problem QA1 is NP-complete when dropping the "planarity & connectedness constraints".

Thanks you for your help,

  • $\begingroup$ @greybeard I am not sure i understand your comment. My questions is not a "homework assignment" if that is what you mean, and all these words are mine so i don't believe any quote is appropriate. These questions sprang out from my research about topology of loops in surfaces, and i tried to formulate them in a language suited to this forum. If they are of a "standard textbook level" i apologize and would be very happy to have references (i guess that's part of what this forum is about : sharing information to answer precise questions). $\endgroup$ Commented Jan 27 at 14:33
  • 1
    $\begingroup$ Please ask only one question per post. If you have multiple questions or multiple problems you want to ask about, each can be posted separately in its own post. $\endgroup$
    – D.W.
    Commented Jan 28 at 6:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.