<p>Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries".</p>

<p>It seems that the existence of a polynomial time algorithm is still open. <a href="http://www.sciencedirect.com/science/article/pii/S0020019000002258">Schmulevich et al.</a> prove that "Almost all monotone Boolean functions are polynomially learnable using membership queries". If we also require that the $t$th minterm be generated in time polynomial in $n$ and $t$, then the problem is equivalent to monotone dualization, as shown by <a href="http://www.sciencedirect.com/science/article/pii/S0890540185711571">Bioch and Ibaraki</a>. Here is a <a href="http://www.sciencedirect.com/science/article/pii/S0166218X07001278">survey</a> addressing monotone dualization.</p>

CC BY-SA 3.0
2012-12-26T17:52:21.690Z
Thanks for this extremely useful answer. Are you aware of generalizations to arbitrary DAGs (i.e., more than the special cases in section 5.2 of Eiter et al.)?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-12-27T03:35:05.317Z
No, unfortunately not.
Yuval Filmus
CC BY-SA 3.0
2012-12-27T17:21:56.750Z
OK, I'll accept this answer anyway. Additional remarks: (1) this answer is about the computational complexity, not the complexity in the number of evaluations of $P$ (see http://cstheory.stackexchange.com/a/14862/4795 for this last case), and (2) the exact open question is "can you learn a monotone boolean function in polynomial time in $n$ and its number of minima and maxima", there is no hope of doing it in polynomial time in $n$ and the number of maxima because there can be a linear number of maxima but an exponential number of minima (cf. sec 6.1 paragraph 2 in the survey mentioned above).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-01-30T00:07:37.117Z
See my other question http://cstheory.stackexchange.com/q/16258/4795 for information about the global worst-case query complexity for arbitrary DAGs.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-02-06T22:00:37.877Z
re monotone dualization (CNF←→DNF) & DAGs. sounds a lot like a theorem from juknas book _boolean function complexity_ sec 9.4. "lower bounds criterion" thm 9.17
vzn
CC BY-SA 3.0
2012-12-20T17:05:34.583Z
2012-12-20T17:05:34.583Z
Yuval Filmus
<p>Consider a <em>monotonic</em> predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking for an algorithm to find all the minimal elements of $P$, i.e., the $x \in 2^{|n|}$ such that $P(x)$ but $\forall y \subset x$, $\neg P(y)$. Since the width of $2^{|n|}$ is $n \choose n/2$, there could be exponentially many minimal elements, and therefore the running time of such an algorithm could be exponential in general. However, could there exist an algorithm for this task which is polynomial in the size of the output?</p>

<p>[Context: A more general question <a href="https://cstheory.stackexchange.com/a/8943/4795">was asked</a> but there was no attempt in the answers to evaluate the complexity of the algorithm in the size of the output. If I assume that there is only one minimal element, for instance, then I can perform a binary search following <a href="https://cstheory.stackexchange.com/questions/8923/binary-search-generalizations-for-posets">this answer</a> and find it. However, if I want to continue finding more minimal elements, I need to maintain the current information I have about $P$ in a way which would make it tractable to continue the search without wasting time on what is already known. Is it possible to do this and find all the minimal elements in polynomial time in the size of the output?]</p>

<p>Ideally, I would like to understand if this can be done with general DAGs, but I already don't know how to answer the question for $2^{|n|}$.</p>

CC BY-SA 3.0
2013-02-07T09:34:26.913Z
The powerset $2^{|n|}$ ordered by inclusion is a DAG (with the various parts of $\{1, ..., n\}$ as vertices and one edges between couples of parts that are included in one another, keeping only the transitive reduction of this graph to remove redundant edges implied by transitivity). It seems natural to ask the same question about arbitrary DAGs.
Antoine Amarilli 'a3nm'
<ds.algorithms><ds.data-structures><partial-order><order-theory><search-problem>
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Antoine Amarilli 'a3nm'
# Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

(Asked by: username_0 on 2012-12-20)

Consider a *monotonic* predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking for an algorithm to find all the minimal elements of $P$, i.e., the $x \in 2^{|n|}$ such that $P(x)$ but $\forall y \subset x$, $\neg P(y)$. Since the width of $2^{|n|}$ is $n \choose n/2$, there could be exponentially many minimal elements, and therefore the running time of such an algorithm could be exponential in general. However, could there exist an algorithm for this task which is polynomial in the size of the output?

[Context: A more general question [was asked](https://cstheory.stackexchange.com/a/8943/4795) but there was no attempt in the answers to evaluate the complexity of the algorithm in the size of the output. If I assume that there is only one minimal element, for instance, then I can perform a binary search following [this answer](https://cstheory.stackexchange.com/questions/8923/binary-search-generalizations-for-posets) and find it. However, if I want to continue finding more minimal elements, I need to maintain the current information I have about $P$ in a way which would make it tractable to continue the search without wasting time on what is already known. Is it possible to do this and find all the minimal elements in polynomial time in the size of the output?]

Ideally, I would like to understand if this can be done with general DAGs, but I already don't know how to answer the question for $2^{|n|}$.

**Tags:** ds.algorithms, ds.data-structures, partial-order, order-theory, search-problem

> **Comments:**
> **username_0**: The powerset $2^{|n|}$ ordered by inclusion is a DAG (with the various parts of $\{1, ..., n\}$ as vertices and one edges between couples of parts that are included in one another, keeping only the transitive reduction of this graph to remove redundant edges implied by transitivity). It seems natural to ask the same question about arbitrary DAGs.  

---

## 1 answers

### Answer by username_1 on 2012-12-20. Score: 14 | Accepted answer

Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries".

It seems that the existence of a polynomial time algorithm is still open. [Schmulevich et al.](http://www.sciencedirect.com/science/article/pii/S0020019000002258) prove that "Almost all monotone Boolean functions are polynomially learnable using membership queries". If we also require that the $t$th minterm be generated in time polynomial in $n$ and $t$, then the problem is equivalent to monotone dualization, as shown by [Bioch and Ibaraki](http://www.sciencedirect.com/science/article/pii/S0890540185711571). Here is a [survey](http://www.sciencedirect.com/science/article/pii/S0166218X07001278) addressing monotone dualization.

> **Comments:**
> **username_0**: Thanks for this extremely useful answer. Are you aware of generalizations to arbitrary DAGs (i.e., more than the special cases in section 5.2 of Eiter et al.)?  
> **username_1**: No, unfortunately not.  
> **username_0**: OK, I'll accept this answer anyway. Additional remarks: (1) this answer is about the computational complexity, not the complexity in the number of evaluations of $P$ (see http://cstheory.stackexchange.com/a/14862/4795 for this last case), and (2) the exact open question is "can you learn a monotone boolean function in polynomial time in $n$ and its number of minima and maxima", there is no hope of doing it in polynomial time in $n$ and the number of maxima because there can be a linear number of maxima but an exponential number of minima (cf. sec 6.1 paragraph 2 in the survey mentioned above).  
> **username_0**: See my other question http://cstheory.stackexchange.com/q/16258/4795 for information about the global worst-case query complexity for arbitrary DAGs.  
> **username_2**: re monotone dualization (CNF←→DNF) & DAGs. sounds a lot like a theorem from juknas book _boolean function complexity_ sec 9.4. "lower bounds criterion" thm 9.17  

---

