I have stumbled across a problem in my free time to which I am struggling to find a fast solution to. It came up when solving systems of equations and can be stated as follows:
Suppose you have a set $S=\{1,…,n\}$ and an unknown but nonempty set of subsets of $S$, $B$. That is, $\forall b \in B, b \subseteq S$. Nothing else about $B$ is known.
Edit: Example: If $S=\{1,2,3,4\}$, then $B$ could for example be $B=\{\{1\}, \{1,2\}, \{3,4\}, \{1,2,3,4\}\}$
Now define a "probe" as an operation, where you give a subset of $S$ to some function and it returns whether it is the superset of some $b \in B$.
The first problem: only using probes, find some element of $B$.
The second problem: only using probes, find the smallest element of $B$.
For the first problem, finding an algorithm, even an $O(n)$ one (in terms of number of probes) is quite straightforward: Let $A$ be the starting set with $A = S$, then, for each number $p \in \{1,…,n\}$, probe $A\backslash p$ . If the probe succeeds, set $A \leftarrow A \backslash p$. Else, continue. After doing this for all $p \in \{1,…,n\}$, it is guarenteed that $A \in B$.
The second problem is much more difficult to solve and I didn't manage to find any even "close to fast" algorithm for it.
I found nothing about it online. I also tried phrasing it as a binary optimization problem in $n$ Dimensions, where the size of the set is optimized, but that didn't get me far.
It relates indirectly to solving a specific limited system of equations, specifically, how many equations can be removed until no variable can be fixed.
My questions are: Is this problem known under another name? Can it be transformed into a more useful/known problem? If yes, is there a faster algorithm for the first problem? And is there a remotely fast (possibly sub-$O(2^n)$) algorithm for the second question?