Complexity in information theory

Authors

Publication date 5 June 1993

The articles of this volume will not be indexed individually. This book is devoted to distinct aspects of measuring information in computation theory. The six contributions selected here do not cover all approaches related to complexity in information theory. But they represent a wide spectrum of relatively new ideas of measuring information for different purposes. Several of these ideas have started new, interesting branches of science. \textit{A. C. Yao} presents in the first chapter ``Computational information theory a new framework for information theory. A reason to do it is in the fact that Shannon's definition of information [\textit{C. E. Shannon}, A mathematical theory of communication, Bell. Syst. Tech. J. 27, 479-453, 623-656 (1948)] is a purely statistical notion, which ignores the computational difficulty of extracting the information. What Yao seeks to accomplish in the new framework is to capture the notion of ``computationally accessible information, and use it to discuss cryptography and pseudorandom number generation, subjects where information and computational complexity are closely intertwined. Chapter II written by \textit{A. Orlitsky} and \textit{A. El Gamal} is devoted to ``communication complexity introduced by \textit{A. C. Yao} [Some complexity questions related to distributive computing, Proc. 11th Ann. ACM Symp. Theory Comput., 209-213 (1979)] and formalized in an abstract model by \textit{C. H. Papadimitriou} and \textit{M. Sipser} [J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064)]. The communication complexity of a Boolean function is the minimum number of bits that must be exchanged between two computers in order to compute the output value by assuming that each computer has access to ``half of the input bits. This complexity measure has proved to be very successful in proving lower bounds on several complexity measures of circuit computations [the reviewer, Comput. Artif. Intell. 7, No.3, 229-252, No.4, 289-302 (1988; Zbl 0644.94027, Zbl 0649.94022), and ibid. 8, for the forthcoming parts \(5+6]\). Orlitsky and El Gamal present here an overview of basic properties of communication complexity considered as an abstract complexity measure. Nondeterminism, randomization, and average case complexity are also included. Chapter III ``Introduction to information-based complexity by \textit{J. F. Traub} gives an informal concept of theory of information-based complexity. In classical complexity theory the information about the problem to be computed is assumed to be complete, exact and free. Here one assumes that information is partial, contamined, and it costs. Several interesting ideas of information-based complexity are discussed. Unfortunately, no formal result or example is presented. So, for readers with some interest the monograph [\textit{J. F. Traub} and \textit{H. Wožniakowski}, A general theory of optimal algorithms (Academic Press, New York 1980; Zbl 0441.68046)] is recommended. \textit{E. B. Baum} presents in Chapter IV the basic concept of complexity theory of learning from examples introduced by \textit{L. G. Valiant} [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)] and some new results showing the existence of ``complete representations able to capture any problem learnable in polynomial time by any representation whatsover. \textit{J. J. Hopfield} considers collective decision networks for solving optimization problems in Chapter V. Simple networks simulating a behaviour of some physical or biological systems are able to solve effectively some NP-hard problems. In the last chapter \textit{Y. S. Abu-Mostafa} introduces the notion ``random problem which may be considered as an extension of the notion random words according to Kolmogorov complexity [\textit{A. N. Kolmogorov}, Probl. Peredachi Inf. 1, 3-11 (1965; Zbl 0271.94018)]. Informally the random problem is such a problem that all algorithms solving it have very large descriptional complexity. Some complexity measures for random problems are defined and some connections to Valiant's learning (loc. cit.) are presented.

Recommendations

Cited in

(13)

This page was built for publication: Complexity in information theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4040887)