# Tag Info

## New answers tagged lower-bounds

1

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it. This will output all of the minimal sets. The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is ...

0

I have found a solution in this paper, p.12. The algorithm mentioned there as proof should translate to the following python code: T = set([]); for x in X: rem = set([]); spe = False; for a in T: rel = oracle(x,a); if rel == "x>a": spe = True; break; elif rel == "x<a": rem.add(a);...

Top 50 recent answers are included