1

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 ?

  • 5
    Have a look at the mastermind game en.wikipedia.org/wiki/Mastermind_(board_game). you will find a lot of stategies and implemenattions on the web – MrSmith42 Nov 20 '15 at 15:22
  • I've checked this page and a few other links but my problem is not exactly the mastermind solving problem, some parameters are fixed and some others are not. I mentionned mastermind because it's a good idea to get the global idea of what I want but I would believe there was a precise algorithm closer to my intent. – ibi0tux Nov 20 '15 at 15:36
  • 2
    Are the assertions in the specified list of criterion 2 contiguous or can that list contain any combination of assertions? – Jan Doggen Nov 20 '15 at 16:19
  • 2
    PROLOG comes to mind. You're basically describing an inference engine. – Robert Harvey Nov 20 '15 at 16:36
  • Yes PROLOG can strongly help me but I would like first to find how 1) generate the minimal set containing subsets I will submit to oracle 2) how to combine the answers to extract values (maybe this part could be apparented to Zebra problem) – ibi0tux Nov 20 '15 at 16:49
4

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.

  • That's what I tried for now, but the main difficulty is to be combine results from oracle to get individual results. For instance assuming the minimum set size is 5 and I have {o(0,1,2,3,4) = 2 , o(5,6,7,8,9) = 1 , o(0,2,4,6,8) = 3 , etc. } how to extract '2', '4' and '6' ? and also how to generate optimal set of subsets that would be required to solve it ? That's the whole complexity of the thing. – ibi0tux Nov 20 '15 at 16:39
3

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(a1,a2,...,an) = 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:

  • Ak = {a1,a2,...,ak-1,ak+1,...,an-1,an}.

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(A1) = c1;
  • true(A2) = c2;
  • ...
  • true(An) = cn.

And finally, the last operation is... Subtraction. You compute the difference between c and every ck 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 a1 from A obtaining the subset A1, and then ask the oracle the value of true(A1).

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

Going on with A2, A3, ..., An and subtracting c to every ck 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.

  • Your answer is interesting. What's a little more complicated is that we have to consider that th minimum input size for the oracle is huge and thus the subsets we have to provide contain a lot of assertions. My thoughts were to work with pairs of sets, and rather generating power set of A, I would generate all combinations of the items in two distinct subsets. But this is obiously not optimal (in the worst case only the half of those combination would suffice). I'm editing my post to give more details. – ibi0tux Nov 20 '15 at 17:07
  • I got your point, I'm editing my current answer to explain a new possible solution. – liggiorgio Nov 21 '15 at 18:29
  • Your way of doing this sounds good except its complexity is linear since it will call the oracle C times (with C the cardinality of A, actually 1+C-1). The complexity of the oracle is also linear you're right, which means the global complexity is polynomial which is unacceptable for my needs. I think we can reduce the number of calls to oracle to something in terms of n*log(C) and I wish there was a proven algorithm for this. – ibi0tux Nov 23 '15 at 10:21
  • You didn't specify your algorithm shall satisfy any level of complexity. Your problem is interesting but I can't keep thinking about a better solution. I strongly suggest you to take a look at "divide-and-conquer" and related metodologies and algorithms, because only by deeply understanding it you will find out a way to make a better algorithm for your purposes. – liggiorgio Nov 24 '15 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.