Complexity and structure
Boolean functionCircuit-Size Complexityexponential hierarchyhigh hierarchylow hierarchyNP-setsOraclespolynomial size circuitspolynomial-time hierarchyProbabilistic Algorithmsrelativizationsselective setsself-reducibilitySparse Setsword problems
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity of proofs (03F20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)
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.
- On sparse oracles separating feasible complexity classes
- Circuit size relative to pseudorandom oracles
- On hiding information from an oracle
- Polynomial time samplable distributions
- Competing provers yield improved Karp-Lipton collapse results
- Sets with small generalized Kolmogorov complexity
- On the lattices of NP-subspaces of a polynomial time vector space over a finite field
- Closure and nonclosure properties of the classes of compressible and rankable sets
- Complexity with Rod
- scientific article; zbMATH DE number 3883613 (Why is no real title available?)
- Circuit-size lower bounds and non-reducibility to sparse sets
- Reducibilities on tally and sparse sets
- On Toda’s Theorem in Structural Communication Complexity
- Sparse Sets, Lowness and Highness
- Immunity and simplicity in relativizations of probabilistic complexity classes
- On problems for which no oracle can help
- scientific article; zbMATH DE number 90342 (Why is no real title available?)
- scientific article; zbMATH DE number 1254496 (Why is no real title available?)
- scientific article; zbMATH DE number 1140233 (Why is no real title available?)
- On a theorem of Razborov
- New collapse consequences of NP having small circuits
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- scientific article; zbMATH DE number 781350 (Why is no real title available?)
- Graph isomorphism is low for PP
- Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
- Average-case intractability vs. worst-case intractability
- On the contribution of backward jumps to instruction sequence expressiveness
- Nondeterministic functions and the existence of optimal proof systems
- Autoreducibility, mitoticity, and immunity
- Complexity-theoretic algebra. II: Boolean algebras
This page was built for publication: Complexity and structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1073788)