Complexity and structure (Q1073788)

The monograph under review is a revised and extended version of the author's dissertation (1981) containing a number of results of other researchers, too. The contents include: Introduction, in which the author gives a brief sketch of the monograph. Chapter 1, Preliminaries. The author introduces notations and definitions which are needed throughout the monograph. Chapter 2, Circuit-Size Complexity. The size of a Boolean function f is the least integer C(f) of arbitrarily chosen 2-ary Boolean functions sufficient to draw up a circuit realizing the function f. For every integer n, the circuit-size complexity of a language \(A\subseteq \{0,1\}^*\), \(CS_ A(n)\), is the minimal size of a Boolean function f such that for any string \(w\in \{0,1\}^*\) of length \(n: f(w)=1\), if \(w\in A\), and \(f(w)=0\), otherwise. This definition is close to the definition of relative complexity of \textit{A. N. Kolmogorov} [Probl. Peredachi Inf. 1, No.1, 3-11 (1965; Zbl 0271.94018)]. A series of results concerning several well-known languages having polynomially bounded circuit-size complexity is given. Chapter 3, Probabilistic Algorithms. The author gives an account of different types of probabilistic algorithms and establishes a link between classes of probabilistic algorithms and polynomial size circuits. Chapter 4, Sparse Sets. A set \(A\subseteq \{0,1\}^*\) is said to be polynomially sparse if for some polynomial P and for every n, the cardinality of the strings of length n, belonging to A, exceeds p(n) [\textit{L. Berman} and \textit{J. Hartmanis}, SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)]. The author expounds a series of results connected with the Berman-Hartmanis conjecture concerning sparse sets in NP. Then he studies ''almost correct'' and ''almost fast'' algorithms in terms of sparse sets. The chapter ends with an investigation of self-reducibility properties of ''almost polynomial type'' sets. \textit{B. A. Trakhtenbrot} [Dokl. Akad. Nauk SSSR 192, 1224- 1227 (1970; Zbl 0216.289)] defined and investigated autoreducible sets. In the monograph the notion of self-reducibility is a restriction of the above mentioned notion of autoreducibility. Chapter 5, The Low and High Hierarchies. This chapter contains results almost entirely obtained by the author. Let \(\Sigma^ p_ k\), \(\Pi^ p_ k\) denote \textit{L. J. Stockmeyer}'s [Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024)] polynomial-time hierarchy and \(\Sigma^ p_ k(A)\), \(\Pi^ p_ k(A)\) be relativized L. J. Stockmeyer hierarchy. The low hierarchy (in NP) is the family of NP-sets A such that \(\Sigma^ p_ k(A)\subseteq \Sigma^ p_ k\) and the high hierarchy (in NP) is the family of sets A such that \(\Sigma^ p_{k+1}\subseteq \Sigma^ p_ k(A)\). The chapter contains a series of results demonstrating links between lowness, highness, completeness, self-reducibility and so on. Chapter 6, Oracles. The chapter is devoted to sensitivity properties of complexity theory in the presence of an oracle. Positive as well as negative relativizations are investigated. The behaviour of oracles in higher levels of the polynomial hierarchy is studied. The monograph is essentially self-contained. A number of open problems are dispersed throughout the monograph.