What is this algorithm?

Question

I would like to implement an algorithm but I guess it's a well-known problem and it has been implemented yet, but I am unable to verify that without its name.

Here is what I am willing to do :

• I have a list of assertions that can be either true or false
• I have an "oracle" that can tell me how many assertions are true among a specified list, but which is unable to tell explicitly which ones are valid or not
• My goal is to know for each assertion if it is true or false
• The "oracle" can only check lists with at least a huge number of assertions (it is not possible to test each assertion one by one)

My approach is to work on subsets (dichotomy seems to be the most efficient way) on my assertion list to divide it in two parts, and submit both parts to the "oracle". After this, I would change the way my assertion list is split and make another test and so on ...

For those who know the game Mastermind this is somehow the idea.

Well, is there any "official" name for this problem and reputed way of solving it ?

Answer 1

I would do it this way:

1. ask the oracle for the list of all assertions. Than you know how many are false
2. Than make a kind of binary search to find each of the failing assertions. You follow each partition in which is still at least one failed assertion until you narrowed down each failing assertion.

Example: 10 assertion

• Oracle(0,1,2,3,4,5,6,7,8,9) = 3 failing assertions
• Oracle(0,1,2,3,4) = 2 | Oracle(5,6,7,8,9) = 1
• Oracle(0,1) = 0 | Oracle(2,3,4) = 2 | Oracle(5,6) = 1 | Oracle(7,8,9) = 0
• Oracle(2) = 1 | Oracle(3,4) = 1 | Oracle(5) = 0 | Oracle(6) = 1
• Oracle (3) = 0 | Oracle(4) = 1

So we know assertion 2,4,6 are the failing assertions

If is there is a minimum size for the list to request, you can request subsets by switching one element until the number changes. If it increases you added a failing assertion. But as a first step I would follow the approach above until you reached the minimal allowed request size.

Answer 2

By answering, I'm assuming that when you say the "oracle" can't tell you if a single assertion is either true o false, it still does know its truth value (e.g. randomly generated truth values for generic assertions).

Let A be the set of your assertions. If A contains n items, its cardinality is: |A| = n. You first ask the oracle how many assertions in the starting set A are true:

• true(A) = true(a₁,a₂,...,a_n) = c.

Now you calculate every subset of cardinality n - 1, thus those subsets containing only n - 1 items; every subset can be defined as follow:

• A_k = {a₁,a₂,...,a_k-1,a_k+1,...,a_n-1,a_n}.

The number of subsets you get is n because you remove one item out of n from time to time.
Again, you ask the oracle how may true assertions are in every subset:

• true(A₁) = c₁;
• true(A₂) = c₂;
• ...
• true(A_n) = c_n.

And finally, the last operation is... Subtraction. You compute the difference between c and every c_k you have, and figure out which assertions are true and which false.

Example: Let's say the set A has 10 items, and true(A) = 5. Half the assertions are true, the other half false. Now we pop out the first assertion a₁ from A obtaining the subset A₁, and then ask the oracle the value of true(A₁).

• If true(A₁) = 5, it means no true assertion was removed from starting set A: a₁ is false;
• If true(A₁) = 4, there's a missing true assertion than before: a₁ is true.

Going on with A₂, A₃, ..., A_n and subtracting c to every c_k will tell you what assertions are true and what false.

Notes: I'm assuming the function true() is linear, because it depends only on the size of input: if the argument size is 50 values, there will be only 50 reading operations. You can implement the function so that its argument is a data structure instead of writing every single variable - that's good for scalability of the input.
The math I used is very simple, and the data structure you need can be whatever you consider appropriate.
Also, you were constrained to ask the oracle for a great number of assertions per time: the smallest sets I dealt with contains n - 1 items, which is very close to the total number of assertions whose value you want to figure out.