<p>I have not thought this through very much, so please correct me if I am wrong.</p>

<p>Say $w$ is the width of the poset.</p>

<ol>
<li><p>For the poset which is the union of $w$ disjoint chains you need at least $w\log n$ evaluations of $P$ by just applying the standard lower bound on the query complexity of binary search to each chain.</p></li>
<li><p>Since you give comparisons for free, you can compute a chain decomposition of the poset into $w$ chains for free. Do binary search on each chain to identify the first element that satisfies $P$. Then go over the identified elements and remove any dominated ones. Number of evaluations of $P$ is $O(w\log n)$. This identifies all maximal elements, as there can be at most one maximal element per chain.</p></li>
</ol>

<hr>

<p><strong>ADDED:</strong> Actually I am seeing a simple recursive algorithm to do much better ($O(n)$) for the lattice of subsets $2^{[n]}$ (<em>EDIT</em>: domotor described the general strategy in his answer). Here I am assuming $P$ is monotonic downwards (i.e. the subsets $\{X: P(X) = 1\}$ form a lower set), which is I think what you mean. So, here is the algorithm to find a member of the lower set:</p>

<p>a) Test $P(\emptyset)$. If 0, then stop.</p>

<p>b) Test $P(\{n\})$.  </p>

<p>b.i) If 0, then recurse on $2^{[n-1]}$ (OK, since no set containing $n$ can be in the lower set). </p>

<p>b.ii) If 1, then there exists a member of the lower set in the sublattice $\{X: n \in X\}$. This sublattice is isomorphic to $2^{[n-1]}$ so once again we can recurse. More precisely, we can run the algorithm for $2^{[n-1]}$, but when the algorithm asks to evaluate $P(Y)$, we evaluate $P(X)$ where $X = Y \cup \{n\}$.</p>

<p>So in each step we recurse on a sublattice which is half the size of original one. Overall, we need to evaluate $P$ at most $2n$ times (in fact you can implement the algorithm to evaluate the predicate $n+1$ times as Yoshio points out, since you only need to check $\emptyset$ once).</p>

CC BY-SA 3.0
2011-11-12T04:23:27.380Z
Wow, such a simple idea! Thanks - I'll give some thought to whether this seems optimal or not :)
jkff
CC BY-SA 3.0
2011-11-12T04:37:59.220Z
It's actually even less than w log n, since the *sum* of chain lengths is n. I guess the maximum is around w log (n/w).
jkff
CC BY-SA 3.0
2011-11-12T04:48:49.847Z
OK, for linear orders this gives binary search, for a subset lattice this gives C(n,n/2) log(2^n/C(n,n/2)) ~ exp(n)*n. Not too fast, but doesn't look too suboptimal either, as there may actually be that many answers. However to find *one* maximal subset, you need binary search over just any *one* chain - this is great and I now call myself stupid for not thinking of it. Thanks again!
jkff
CC BY-SA 3.0
2011-11-12T04:49:41.670Z
For a 2d grid this gives us log(n) to find one answer and n log n to find all of them - but I think we can do O(n) to find all answers.
jkff
CC BY-SA 3.0
2011-11-12T05:25:45.353Z
@jkff: To find a single maximal subset, how do you know which chain to do binary search over? There are ${n \choose n/2}$ of them. I added another algorithm specifically for finding a single subset in a subset lattice, but if you see a way in which the general strategy already works for that (in time poly in $n$), let me know.
Sasho Nikolov
CC BY-SA 3.0
2011-11-12T08:59:45.727Z
I am afraid that the algorithm is incorrect :( consider A>C, B>C, P(B),P(C). then there exists a chain decomposition (AB, C) and the solution in chain AB is not a global solution.
jkff
CC BY-SA 3.0
2011-11-12T09:04:56.530Z
By the way, a perhaps more interesting problem is to consider the poset of subsets of S where sets are compared by number of elements instead of by inclusion. This is no longer a lattice, but seems more practically interesting.
jkff
CC BY-SA 3.0
2011-11-12T09:09:39.893Z
Also the subsets satisfying P do not seem to form an ideal to me: this is a lower set but not closed under joins. Am I misunderstanding something? (I've just read the definition of ideal in Wikipedia)
jkff
CC BY-SA 3.0
2011-11-12T10:40:29.517Z
@jkff i don't understand, if the poset is given by A>C and B>C, then how is A-B a chain? Did you mean decomposition is CA, B, and the solution C in chain CA is not global. That's a good point, but easy to fix: there is a post-processing step I left out. I will edit the solution
Sasho Nikolov
CC BY-SA 3.0
2011-11-12T10:45:32.430Z
ok, so in the terminology on wikipedia what I head in mind is what they call a lower set. maybe I had my definitions wrong.
Sasho Nikolov
CC BY-SA 3.0
2011-11-12T13:54:37.983Z
You're right, I meant AC obviously. The problem with postprocessing is that it only helps find all answers, not any one.
jkff
CC BY-SA 3.0
2011-11-12T15:22:00.557Z
@Sasho: This simple recursive algorithm is exactly the same as my algorithm for the special case $2^{[n]}$.
domotorp
CC BY-SA 3.0
2011-11-12T15:36:08.637Z
You could imagine the algorithm as hill-climbing.  The number of evaluations can be bounded by n+1 since you don't have to evaluate for $\emptyset$ in the recursive calls (we already know the outcome is 1).
Yoshio Okamoto
CC BY-SA 3.0
2011-11-12T20:24:10.483Z
@domotorp You're right, I am sorry about that. I will leave it here because I think I included more detail, but I will ref your answer
Sasho Nikolov
CC BY-SA 3.0
2011-11-12T20:25:02.383Z
@jkff I never understood your point about finding a single element. Even if you could search just one chain, I don't think you can know apriori which one.
Sasho Nikolov
CC BY-SA 3.0
2011-11-13T02:40:12.010Z
Well, my point is "I think there should be a way to find one solution faster than finding all solutions" - is your point the opposite?
jkff
CC BY-SA 3.0
2011-11-13T03:02:40.687Z
I think $w$ disjoint chains give you a lower bound of at least $w + \log n$ (for deterministic algorithms). Think of an adversary who "hides" a single solution in the last chain queried. A randomized lower bound of $\Omega(w)$ should follow from Yao's minimax principle.  Finding a single element with complexity $w + \log n$ might be interesting.
Sasho Nikolov
CC BY-SA 3.0
2014-12-01T13:50:30.753Z
Is it very special for a lattice to be a union of disjoint chains?  What is the criterion?
Yan King Yin
CC BY-SA 3.0
2014-12-01T18:36:31.513Z
@YanKingYin A lattice cannot be the union of (more than one) disjoint chains, because each two elements must have a supremum. A poset is a union of disjoint chains if it can be partitioned so that elements from different parts are incomparable and elements within the same part admit a total order.
Sasho Nikolov
CC BY-SA 3.0
2014-12-02T12:51:13.813Z
But 2 elements of a lattice can still be incomparable, right?  Posets are a superclass of lattices, right?  If we regard the lattice as a poset then it can be decomposed according to incomparability... right?
Yan King Yin
CC BY-SA 3.0
2014-12-02T19:58:30.043Z
Of course two elements $x, y$ of a lattice can be incomparable but there will be a third element $z$ such that $x < z$ and $y < z$. This does not happen in a poset which is a disjoint union of chains. Lattices are special posets, and I don't understand your last question.
Sasho Nikolov
CC BY-SA 3.0
2011-11-11T22:43:44.883Z
2011-11-12T20:27:16.813Z
2011-11-12T20:27:16.813Z
Sasho Nikolov
<p>If $P$ is a tree, then there is a polynomial-time algorithm that constructs an optimal decision tree.</p>

<p><a href="http://people.csail.mit.edu/konak/papers/focs_2006-generalization_of_binary_search.html">Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders</a></p>

CC BY-SA 3.0
2011-11-12T11:11:34.347Z
2011-11-12T11:11:34.347Z
ilyaraz
<p><a href="http://arxiv.org/abs/0707.1532">One recent paper</a> by Daskalakis et al shows that for a poset of size $n$ and width $w$, minimal elements can be found in time $O(wn)$. What's interesting is that in their abstract, they say </p>

<blockquote>
  <p>It would also be interesting to find efficient static and dynamic data
  structures that play the same role for partial orders that heaps and
  binary search trees play for total orders.</p>
</blockquote>

CC BY-SA 3.0
2011-11-11T05:46:57.110Z
Heh, sounds not too inspiring compared to log(n) :) but thanks anyways!
jkff
CC BY-SA 3.0
2011-11-11T14:29:58.013Z
But that's the point. Without data structures you can't get log n even for s totally ordered set, because all you can do is scan. It's actually a really nice question to try and find a BST equivalent.
Suresh Venkat
CC BY-SA 3.0
2011-11-11T15:08:12.380Z
Well - I'm talking about the complexity in terms of the number of evaluations of predicate P, not the comparison predicate.
jkff
CC BY-SA 3.0
2011-11-11T16:20:07.860Z
I see. So actually in your case you'd like a decomposition into the ideals and then examine the roots
Suresh Venkat
CC BY-SA 3.0
2011-11-11T18:05:18.143Z
In a sense yes, but that's far from being the complete answer — eg it doesn't give bisection for the 1d or 2d cases :) what do you suggest to do with the roots?
jkff
CC BY-SA 3.0
2011-11-11T18:07:47.443Z
Not sure yet. thinking out loud. But it's an excellent question.
Suresh Venkat
CC BY-SA 3.0
2011-11-11T04:58:41.107Z
2011-11-11T04:58:41.107Z
Suresh Venkat
<p>For the problem of finding all the maximal elements of $P$ over the lattice of subsets $2^{[n]}$, this amounts to exact inference of a positive boolean function of $n$ boolean variables. If you only care about the number of evaluations of $P$ (not the computational complexity), you can find a survey in <em>Data Mining and Knowledge Discovery via Logic-Based Methods</em>, Chapter 10, section 10.2.4, or in the last paragraph of section 6.1 of <a href="http://www.sciencedirect.com/science/article/pii/S0166218X07001278" rel="nofollow noreferrer">this article</a>, which I was pointed to by <a href="https://cstheory.stackexchange.com/a/14780/4795">this answer</a> (beware, the rest of this article deals with computational complexity, not just the complexity of evaluating $P$).</p>

CC BY-SA 3.0
2012-12-26T17:50:25.433Z
2012-12-26T17:50:25.433Z
2017-04-13T12:32:28.077Z
Antoine Amarilli 'a3nm'
<p>If S is part of the input, then the problem of finding a maximal element already becomes ``NP-hard'' (if we think of the lattice such that its elements are n bit long strings), e.g. you can say $x&lt;y$ if CNF(x) is not true and CNF(y) is true for some fixed CNF.</p>

<p>Also, there might be many maximal elements satisfying P, so even to output all of them might take a long time, so I think there is only hope to find one maximal.</p>

<p>In general, binary search works if you can recursively select elements such that after you are left either with the above elements, or the above elements are deleted, and in every such sets a fixed ratio of the elements are deleted.</p>

<p>Eg. if S is a fixed dimensional grid, then there is a fast algorithm: Always halve one coordinate while keeping the others minimal, so ask e.g. in the first step (n/2,0,...,0). </p>

<p>One important related theorem is the Tarski fixed point theorem, where instead of P you have a monotone mapping from a lattice to itself. The theorem says that the fixed points form a lattice. We proved with Jaroslaw Byrka and Paul Duetting that in this setting if the lattice is a d-dimensional grid, then you can find a fixed point in about $n^d$ time where the algorithm is a simple generalization of binary search.</p>

CC BY-SA 3.0
2011-11-11T13:04:44.670Z
I'm afraid I don't understand the first paragraph.  In your reduction, do you have all n-bit strings in the poset S and are they given as part of the input?  If so, we can go through all strings in polynomial time.
Yoshio Okamoto
CC BY-SA 3.0
2011-11-11T16:06:53.710Z
@YoshioOkamoto: I think that the assumption in that paragraph is that the comparison in S is given as a Boolean circuit.  (But that has nothing to do with search in a poset and therefore not interesting to me.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-11T22:16:04.693Z
@Tsuyoshi: Thank you.  That makes a lot of sense.
Yoshio Okamoto
CC BY-SA 3.0
2011-11-11T10:55:23.360Z
2011-11-12T22:04:02.527Z
2011-11-12T22:04:02.527Z
domotorp
<p>Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.</p>

<p><strong>EDIT</strong>: I'm interested in minimizing the number of <strong>evaluations of P</strong>.</p>

<p>What algorithms do there exist for this problem and what properties and additional operations do they require on S?</p>

<p>What about important special cases, such as:</p>

<ul>
<li> S is a linear order - then regular binary search works, as long as you have a "find middle" operation
<li> S is a lattice
<li> S is a subset lattice
<li> S is a multiset lattice
<li> ...
</ul>

<p>The two latter cases seem particularly important e.g. for experiment design - you have a set of boolean or real parameters, and you wish to find the smallest possible combination of them that reproduces a particular pattern (e.g. a failing test).</p>

CC BY-SA 3.0
2011-11-11T04:45:49.377Z
What's the 'multiset' lattice ?
Suresh Venkat
CC BY-SA 3.0
2011-11-11T05:45:26.770Z
It's the lattice whose elements are mappings X -> N, meet is elementwise min and join is elementwise max. It can be generalized to any lattice instead of N as the codomain.
jkff
<ds.algorithms><ds.data-structures><partial-order><order-theory><search-problem>
Binary search generalizations for posets?
jkff
# Binary search generalizations for posets?

(Asked by: username_0 on 2011-11-11)

Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.

**EDIT**: I'm interested in minimizing the number of **evaluations of P**.

What algorithms do there exist for this problem and what properties and additional operations do they require on S?

What about important special cases, such as:

* S is a linear order - then regular binary search works, as long as you have a "find middle" operation* S is a lattice* S is a subset lattice* S is a multiset lattice* ...

The two latter cases seem particularly important e.g. for experiment design - you have a set of boolean or real parameters, and you wish to find the smallest possible combination of them that reproduces a particular pattern (e.g. a failing test).

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

> **Comments:**
> **username_1**: What's the 'multiset' lattice ?  
> **username_0**: It's the lattice whose elements are mappings X -> N, meet is elementwise min and join is elementwise max. It can be generalized to any lattice instead of N as the codomain.  

---

## 5 answers

### Answer by username_2 on 2011-11-11. Score: 16

I have not thought this through very much, so please correct me if I am wrong.

Say $w$ is the width of the poset.

1. For the poset which is the union of $w$ disjoint chains you need at least $w\log n$ evaluations of $P$ by just applying the standard lower bound on the query complexity of binary search to each chain.
2. Since you give comparisons for free, you can compute a chain decomposition of the poset into $w$ chains for free. Do binary search on each chain to identify the first element that satisfies $P$. Then go over the identified elements and remove any dominated ones. Number of evaluations of $P$ is $O(w\log n)$. This identifies all maximal elements, as there can be at most one maximal element per chain.

---

**ADDED:** Actually I am seeing a simple recursive algorithm to do much better ($O(n)$) for the lattice of subsets $2^{[n]}$ (*EDIT*: domotor described the general strategy in his answer). Here I am assuming $P$ is monotonic downwards (i.e. the subsets $\{X: P(X) = 1\}$ form a lower set), which is I think what you mean. So, here is the algorithm to find a member of the lower set:

a) Test $P(\emptyset)$. If 0, then stop.

b) Test $P(\{n\})$.

b.i) If 0, then recurse on $2^{[n-1]}$ (OK, since no set containing $n$ can be in the lower set).

b.ii) If 1, then there exists a member of the lower set in the sublattice $\{X: n \in X\}$. This sublattice is isomorphic to $2^{[n-1]}$ so once again we can recurse. More precisely, we can run the algorithm for $2^{[n-1]}$, but when the algorithm asks to evaluate $P(Y)$, we evaluate $P(X)$ where $X = Y \cup \{n\}$.

So in each step we recurse on a sublattice which is half the size of original one. Overall, we need to evaluate $P$ at most $2n$ times (in fact you can implement the algorithm to evaluate the predicate $n+1$ times as Yoshio points out, since you only need to check $\emptyset$ once).

> **Comments:**
> **username_0**: Wow, such a simple idea! Thanks - I'll give some thought to whether this seems optimal or not :)  
> **username_0**: It's actually even less than w log n, since the *sum* of chain lengths is n. I guess the maximum is around w log (n/w).  
> **username_0**: OK, for linear orders this gives binary search, for a subset lattice this gives C(n,n/2) log(2^n/C(n,n/2)) ~ exp(n)*n. Not too fast, but doesn't look too suboptimal either, as there may actually be that many answers. However to find *one* maximal subset, you need binary search over just any *one* chain - this is great and I now call myself stupid for not thinking of it. Thanks again!  
> **username_0**: For a 2d grid this gives us log(n) to find one answer and n log n to find all of them - but I think we can do O(n) to find all answers.  
> **username_2**: @username_0: To find a single maximal subset, how do you know which chain to do binary search over? There are ${n \choose n/2}$ of them. I added another algorithm specifically for finding a single subset in a subset lattice, but if you see a way in which the general strategy already works for that (in time poly in $n$), let me know.  
> **username_0**: I am afraid that the algorithm is incorrect :( consider A>C, B>C, P(B),P(C). then there exists a chain decomposition (AB, C) and the solution in chain AB is not a global solution.  
> **username_0**: By the way, a perhaps more interesting problem is to consider the poset of subsets of S where sets are compared by number of elements instead of by inclusion. This is no longer a lattice, but seems more practically interesting.  
> **username_0**: Also the subsets satisfying P do not seem to form an ideal to me: this is a lower set but not closed under joins. Am I misunderstanding something? (I've just read the definition of ideal in Wikipedia)  
> **username_2**: @username_0 i don't understand, if the poset is given by A>C and B>C, then how is A-B a chain? Did you mean decomposition is CA, B, and the solution C in chain CA is not global. That's a good point, but easy to fix: there is a post-processing step I left out. I will edit the solution  
> **username_2**: ok, so in the terminology on wikipedia what I head in mind is what they call a lower set. maybe I had my definitions wrong.  
> **username_0**: You're right, I meant AC obviously. The problem with postprocessing is that it only helps find all answers, not any one.  
> **username_3**: @Sasho: This simple recursive algorithm is exactly the same as my algorithm for the special case $2^{[n]}$.  
> **username_4**: You could imagine the algorithm as hill-climbing.  The number of evaluations can be bounded by n+1 since you don't have to evaluate for $\emptyset$ in the recursive calls (we already know the outcome is 1).  
> **username_2**: @username_3 You're right, I am sorry about that. I will leave it here because I think I included more detail, but I will ref your answer  
> **username_2**: @username_0 I never understood your point about finding a single element. Even if you could search just one chain, I don't think you can know apriori which one.  
> **username_0**: Well, my point is "I think there should be a way to find one solution faster than finding all solutions" - is your point the opposite?  
> **username_2**: I think $w$ disjoint chains give you a lower bound of at least $w + \log n$ (for deterministic algorithms). Think of an adversary who "hides" a single solution in the last chain queried. A randomized lower bound of $\Omega(w)$ should follow from Yao's minimax principle.  Finding a single element with complexity $w + \log n$ might be interesting.  
> **username_5**: Is it very special for a lattice to be a union of disjoint chains?  What is the criterion?  
> **username_2**: @YanKingYin A lattice cannot be the union of (more than one) disjoint chains, because each two elements must have a supremum. A poset is a union of disjoint chains if it can be partitioned so that elements from different parts are incomparable and elements within the same part admit a total order.  
> **username_5**: But 2 elements of a lattice can still be incomparable, right?  Posets are a superclass of lattices, right?  If we regard the lattice as a poset then it can be decomposed according to incomparability... right?  
> **username_2**: Of course two elements $x, y$ of a lattice can be incomparable but there will be a third element $z$ such that $x < z$ and $y < z$. This does not happen in a poset which is a disjoint union of chains. Lattices are special posets, and I don't understand your last question.  

---

### Answer by username_6 on 2011-11-12. Score: 9

If $P$ is a tree, then there is a polynomial-time algorithm that constructs an optimal decision tree.

[Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders](http://people.csail.mit.edu/konak/papers/focs_2006-generalization_of_binary_search.html)


---

### Answer by username_1 on 2011-11-11. Score: 8

[One recent paper](http://arxiv.org/abs/0707.1532) by Daskalakis et al shows that for a poset of size $n$ and width $w$, minimal elements can be found in time $O(wn)$. What's interesting is that in their abstract, they say

> It would also be interesting to find efficient static and dynamic data
> structures that play the same role for partial orders that heaps and
> binary search trees play for total orders.

> **Comments:**
> **username_0**: Heh, sounds not too inspiring compared to log(n) :) but thanks anyways!  
> **username_1**: But that's the point. Without data structures you can't get log n even for s totally ordered set, because all you can do is scan. It's actually a really nice question to try and find a BST equivalent.  
> **username_0**: Well - I'm talking about the complexity in terms of the number of evaluations of predicate P, not the comparison predicate.  
> **username_1**: I see. So actually in your case you'd like a decomposition into the ideals and then examine the roots  
> **username_0**: In a sense yes, but that's far from being the complete answer — eg it doesn't give bisection for the 1d or 2d cases :) what do you suggest to do with the roots?  
> **username_1**: Not sure yet. thinking out loud. But it's an excellent question.  

---

### Answer by username_7 on 2012-12-26. Score: 5

For the problem of finding all the maximal elements of $P$ over the lattice of subsets $2^{[n]}$, this amounts to exact inference of a positive boolean function of $n$ boolean variables. If you only care about the number of evaluations of $P$ (not the computational complexity), you can find a survey in *Data Mining and Knowledge Discovery via Logic-Based Methods*, Chapter 10, section 10.2.4, or in the last paragraph of section 6.1 of [this article](http://www.sciencedirect.com/science/article/pii/S0166218X07001278), which I was pointed to by [this answer](https://cstheory.stackexchange.com/a/14780/4795) (beware, the rest of this article deals with computational complexity, not just the complexity of evaluating $P$).


---

### Answer by username_3 on 2011-11-11. Score: 4

If S is part of the input, then the problem of finding a maximal element already becomes ``NP-hard'' (if we think of the lattice such that its elements are n bit long strings), e.g. you can say $x

Also, there might be many maximal elements satisfying P, so even to output all of them might take a long time, so I think there is only hope to find one maximal.

In general, binary search works if you can recursively select elements such that after you are left either with the above elements, or the above elements are deleted, and in every such sets a fixed ratio of the elements are deleted.

Eg. if S is a fixed dimensional grid, then there is a fast algorithm: Always halve one coordinate while keeping the others minimal, so ask e.g. in the first step (n/2,0,...,0).

One important related theorem is the Tarski fixed point theorem, where instead of P you have a monotone mapping from a lattice to itself. The theorem says that the fixed points form a lattice. We proved with Jaroslaw Byrka and Paul Duetting that in this setting if the lattice is a d-dimensional grid, then you can find a fixed point in about $n^d$ time where the algorithm is a simple generalization of binary search.

> **Comments:**
> **username_4**: I'm afraid I don't understand the first paragraph.  In your reduction, do you have all n-bit strings in the poset S and are they given as part of the input?  If so, we can go through all strings in polynomial time.  
> **username_8**: @YoshioOkamoto: I think that the assumption in that paragraph is that the comparison in S is given as a Boolean circuit.  (But that has nothing to do with search in a poset and therefore not interesting to me.)  
> **username_4**: @Tsuyoshi: Thank you.  That makes a lot of sense.  

---

