Complexity in information theory (Q4040887)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 194098
Language Label Description Also known as
default for all languages
No label defined
    English
    Complexity in information theory
    scientific article; zbMATH DE number 194098

      Statements

      5 June 1993
      0 references
      Complexity
      0 references
      Information theory
      0 references
      computational complexity
      0 references
      learnability
      0 references
      Turing machines. Computational information theory
      0 references
      cryptography
      0 references
      pseudorandom number generation
      0 references
      communication complexity
      0 references
      complexity measure
      0 references
      circuit computations
      0 references
      Kolmogorov complexity
      0 references
      Complexity in information theory (English)
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references