# Maximal Elements in a Lower Set

I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things will fit into a certain-sized packing crate.

I want to compute all feasible sets (equivalently - all maximal feasible sets), minimizing the number of evaluations of the feasibility property (worst-case or average). Does anyone know of any theoretical work on this?

Bonus question - what if the cost to compute the property is linear (or superlinear) in the size of the set being evaluated?

If the only queries you allow are membership queries (test whether a given set is feasible or not) then your problem is rather difficult. Theorem 2 in Angluin's Queries and Concept Learning shows that $2^n-1$ queries are required even if there are only $2n$ objects and $n+1$ minterms. See the paper for other models in which your problem can be solved efficiently.