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.

  • 1
    $\begingroup$ 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.) $\endgroup$ – j_random_hacker Nov 25 '16 at 14:50
  • $\begingroup$ @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. $\endgroup$ – kjo Nov 25 '16 at 14:56
  • 2
    $\begingroup$ 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.) $\endgroup$ – j_random_hacker Nov 25 '16 at 15:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Willard Zhan Nov 25 '16 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.