# Monotone boolean satisfiability problem : finding minimal solutions

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".

• @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). Commented Jan 27 at 14:33
• 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.
– D.W.
Commented Jan 28 at 6:06