Strategies for the Renyi-Ulam Game with fixed number of lies

Deppe C (2004)
THEORETICAL COMPUTER SCIENCE 314(1-2): 45-55.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
We consider the problem of finding the minimal number L-l(M) of binary questions needed to find an unknown element of a set of cardinality M with a sequential strategy if at most I of the answers are lies. Obviously, in the case l = 0 [logM] questions are needed. Thus, one more question is necessary if the number of elements is doubled. We show that for every fixed 1 and sufficiently large M, then L-l(2M) less than or equal to L-l(M)+2 and moreover L-l((3)/M-2) less than or equal to L-l(M)+1. These bounds are sharp in infinitely many cases. As a consequence, at most one question more than the information theoretic lower bound is needed to successfully find the unknown number. One of our strategies uses the minimum amount of adaptiveness during the search process. (C) 2003 Elsevier B.V. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
THEORETICAL COMPUTER SCIENCE
Band
314
Zeitschriftennummer
1-2
Seite
45-55
ISSN
PUB-ID

Zitieren

Deppe C. Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE. 2004;314(1-2):45-55.
Deppe, C. (2004). Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE, 314(1-2), 45-55. doi:10.1016/j.tcs.2003.10.036
Deppe, C. (2004). Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE 314, 45-55.
Deppe, C., 2004. Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE, 314(1-2), p 45-55.
C. Deppe, “Strategies for the Renyi-Ulam Game with fixed number of lies”, THEORETICAL COMPUTER SCIENCE, vol. 314, 2004, pp. 45-55.
Deppe, C.: Strategies for the Renyi-Ulam Game with fixed number of lies. THEORETICAL COMPUTER SCIENCE. 314, 45-55 (2004).
Deppe, Christian. “Strategies for the Renyi-Ulam Game with fixed number of lies”. THEORETICAL COMPUTER SCIENCE 314.1-2 (2004): 45-55.