Least number of guesses needed to determine all unknown subsets of a set
A simple algorithm may be:

Loop on:


take the next unassigned element Ei and create a new set Si assigning Ei to it.
loop on all unassigned elements Ej, testing the pair {Ei,Ej}. If it is true, assign j it to Si.


In worst case, this is O(kn) as you won't do this loop more than k times. In average case, I am not sure...