3
$\begingroup$

I have the following problem:

There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'), and it is known that the test outcome only depends on a value of a single variable being larger than some threshold. That is, the outcome is 'Pass' if $x_k \ge c$ and 'Fail' if $x_k < c$. My goal is to find $k$ and $c$ (i.e. which variable is causing the failure and what is the threshold).

My thinking so far is as follows: if I know $k$ and only need to find $c$, than I can do a binary search and find the threshold in $\log_2 m$ steps. If I know $c$ and don't know $k$, I can similarly find it in $\log_2 n$ steps (by setting half of the variables to a value above the threshold and the other half to a value below, thus excluding half of the possibilities, etc.).

I can also first find $c$ in a similar way using a binary search, each time setting all the variables to the same value, and afterwards find $k$ as before. This will take a total of $\log_2 m + \log_2 n = \log_2 nm$ steps.

It seems however that this might not be the optimal approach. So my question is: Is there an algorithm that can find the answer in less than $\log_2 nm$ steps ?

(also, if someone has a suggestion for improving the title of this question, that would be welcome)

$\endgroup$
0

1 Answer 1

2
$\begingroup$

No, it's not possible to use fewer steps than that. Each test gives you one bit of information about the solution. There are $nm$ possible solutions, so you need $\lg(nm)$ bits of information to uniquely identify the solution -- which means you need at least $\lg(nm)$ tests.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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