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,

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,

Consider a 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 sub-poset 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,

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,