Abstract
The problem is considered of identifying an unknown value x belonging left brace 1,2,. . . ,n right brace using only comparisons of x to constants when as many as E of the comparisons may receive erroneous answers. For a continuous analog of this problem it is shown that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log//2n plus E multiplied by (times) log//2log//2n plus O(E multiplied by (times) log//2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary ″Yes-No″ questions are allowed. It is shown that a modified version of this search problem with errors is equivalent to the problem of finding the minimal root of a set of increasing functions. The modified version is then also shown to be of complexity log//2n plus E multiplied by (times) log//2log//2n plus O(E multiplied by (times) log//2E).
Original language | English (US) |
---|---|
Title of host publication | Unknown Host Publication Title |
Publisher | ACM |
Pages | 227-232 |
Number of pages | 6 |
State | Published - 1978 |
Event | Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA Duration: May 1 1978 → May 3 1978 |
Other
Other | Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp |
---|---|
City | San Diego, CA, USA |
Period | 5/1/78 → 5/3/78 |
ASJC Scopus subject areas
- General Engineering