# What's the name of this problem? (Search for minimal satisfying sets)

NB: I've been trying to Google for prior work on the problem described later in this post, but the search results I get for all the keywords I can come up with (e.g. minimal satisfying sets) are inundated with false positives. In this post I'm just asking for terminology/nomenclature/buzzwords to make my Google searches more specific.

First, some assumptions and definitions.

We restrict our attention to subsets of some finite set $U$. (IOW, below, a "set" is shorthand for a "subset of $U$".)

Let $p$ be a predicate on sets such that

$$(p(A) \land (A \subseteq B)) \Longrightarrow p(B).$$

Let's say that a set $A$ is satisfying iff $p(A)$. If $A$ is satisfying, and no proper subset of $A$ is satisfying, then we'll say that $A$ is a minimal satisfying set.

The problem is:

Find all the minimal satisfying sets.

More specifically, I'm looking for algorithms to find all minimal satisfying sets optimally (or at least efficiently).

I should mention a variant of this problem that I'm particularly interested in, just in case it goes by a different name. This variant is the special case of the above where $p(U)$ holds. IOW, we know that there is at least one satisfying set.

• First, Sperner's Theorem implies that there could be more than polynomially many minimal satisfying sets, so that rules out a poly-time algorithm. (Summary of the counterexample: $p(A)$ holds for exactly those sets containing $|U|/2$ elements.) – j_random_hacker Nov 25 '16 at 14:50
• @j_random_hacker: by assumption, if $p(A)$, then $p(B)$ for every superset of $A$, so your counterexample cannot arise given the problem statement. – kjo Nov 25 '16 at 14:56
• Sorry, I meant to say that $p(A)$ holds for sets containing at least $|U|/2$ elements; this leaves the superpolynomial number of sets having exactly $|U|/2$ elements as the minimal satisfying sets. (No set containing exactly |U|/2 elements can be a superset of any other such set, since they have the same number of elements.) – j_random_hacker Nov 25 '16 at 15:01
• I suggest learning monotone boolean functions, and if you don't want stochastic algorithms used mainly in learning theory, you can add the key word deterministic. – Willard Zhan Nov 25 '16 at 15:32