Variations on the theme of “twenty questions”

Summary form only given. One of the aims of computational complexity theory is to derive lower and upper bounds on the complexity of particular computational problems within particular models of computation. In many of these models computation can be viewed as the acquisition of information about an unknown object and elementary concepts from information theory, such as entropy and Kolmogorov complexity, naturally come into play