We have

  1. Some big hashed array of data with boolean values, we know keys, but don't know values.
  2. Oracle who have input of array of keys and can tell how much of them are true (it Answers with number T)

Number of keys N, true values M, for example M/N = 0.4

How to find a way to make own array of keys, length be M and if we ask oracle about those keys we should get T/M > 0.8 with minimum as possible questions to oracle ?

I tried to divide array by halfs and check which is bigger, and so on, but not moved far on this way. number of questions when testing was far more than N.


// test = {a: true, b: false, c: true, d: false}` M=2 N=4
T=oracle(["a", "b"]) //1
T=oracle(["a", "c", "d"])  //2

//we searching for a and c keys
T=oracle(["c", "b"]) //1
areWeDone(T/M) > 0.8 // 0.4 (false)
T=oracle(["a", "c"]) //2
areWeDone(T/M) > 0.8 // 1 (true) 
  • $\begingroup$ I'm not sure you can do better than trying all keys one by one until you find a true one. In particular, it seems that you cannot implement binary search, since copying an array of length $\ell$ already takes $\Omega(\ell)$ time. $\endgroup$ – Yuval Filmus Jun 27 '17 at 20:01
  • $\begingroup$ also the array is big and oracle is to slow to ask him often (in my practical problem it answers once per day, but I can ask him to answer to several questions in parallel, not more than 20, my practical array is about 3 million records) $\endgroup$ – zb' Jun 28 '17 at 3:49
  • $\begingroup$ Are you trying to minimize the number of oracle calls, or the running time? Actually, what is your question? I see only a bunch of statements, but no question. I guess the question isn't "is there an algorithm to solve this" as you already know an algorithm -- it's just slower than you'd like. So what is your question? $\endgroup$ – D.W. Jun 28 '17 at 4:10
  • $\begingroup$ @D.W. Fixed some in question, the array we "found" should have length N. I trying to minimize oracle calls. $\endgroup$ – zb' Jun 28 '17 at 4:33
  • $\begingroup$ is that M in "array of keys, length be M" given, or can I choose an M I like to reach 80% T? $\endgroup$ – CFrei Jun 28 '17 at 7:24

Your Answer

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

Browse other questions tagged or ask your own question.