Structural complexity II
Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
This second volume introduces several models for parallel computation and the corresponding complexity classes, the parallel computation thesis is then discussed. Alternating turing machines (a special parallel model) is considered in Chapter 3. Chapter 4 introduces uniform circuit complexity, its relation to the models studied so far, and discusses the class NC. Starting from Chapter 6, the book discusses several typical issues from structural complexity theory, such as the Berman-Hartmanis isomorphism conjecture and sparse sets; bi-immunity and complexity cores are considered in Chapter 6. Oracles and relativizational results (e.g. relativized separations and strong separations of \(P\) and \(NP\)) are presented in Chapter 7. Positive relativizations, i.e. oracle results that are conform with the absolute case are introduced in Chapter 8. In Chapter 9, the low hierarchy and the high hierarchy (as generalization of the \(NP\)-completeness notion) are considered that turn out to be useful in classifying \(NP\)-problems, but in a variant also problems outside \(NP\). Many of the previous results (e.g. on sparse sets) can be better understood and presented in more generality using (resource-bounded) Kolmogorov-complexity (Chapter 10). In Chapter 11, probabilistic complexity classes and interactive proof systems are considered (that can be used to characterize the graph isomorphism problem). The appendix presents a proof of the Immerman/Szelepcsényi counting technique for complementing nondeterministic sparse classes.
- Theory of one-tape linear-time Turing machines
- On random oracle separations
- A survey of space complexity
- NC algorithms for real algebraic numbers
- Complexity of logical theories involving coprimality
- Unambiguity of circuits
- Exponential-time and subexponential-time sets
- A positive relativization of polynomial time versus polylog space
- Some complexity bounds for subtype inequalities
- Saturation and stability in the theory of computation over the reals
- The relative power of logspace and polynomial time reductions
- On symmetric differences of NP-hard sets with weakly P-selective sets
- Some descriptive-set-theoretical problems in complexity theory
- Locating P/poly optimally in the extended low hierarchy
- On resource-bounded instance complexity
- An excursion to the Kolmogorov random strings
- Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
- Separating classes in the exponential-time hierarchy from classes in PH
- An oracle builder's toolkit
- Optimal proof systems imply complete sets for promise classes
- The zero-one law holds for BPP
- Some aspects of studying an optimization or decision problem in different computational models
- Bounded queries, approximations, and the Boolean hierarchy
- Sparse sets and collapse of complexity classes
- The guarded fragment with transitive guards
- Bi-immunity separates strong NP-completeness notions
- On logics with two variables
- Two queries
- Hard sets are hard to find
- Data independence of read, write, and control structures in PRAM computations
- The polynomial hierarchy of functions and its levels
- Polylog depth, highness and lowness for E
- Weak completeness notions for exponential time
- On some derivation mechanisms and the complexity of their Szilard languages
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- Baire categories on small complexity classes and meager-comeager laws
- Graph Isomorphism is in SPP
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
- A reducibility for the dot-depth hierarchy
- Resource bounded immunity and simplicity
- Cluster computing and the power of edge recognition
- Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
- End-extensions of models of weak arithmetic from complexity-theoretic containments
- Limits to measurement in experiments governed by algorithms
- Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
- Complexity issues for preorders on finite labeled forests
- Recursion Schemata for NC k
- On Toda’s Theorem in Structural Communication Complexity
- Nontriviality for exponential time w.r.t. weak reducibilities
- The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\)
- scientific article; zbMATH DE number 90342 (Why is no real title available?)
- Logics which capture complexity classes over the reals
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- Language classes defined by time-bounded relativised cellular automata
- An observation on probability versus randomness with applications to complexity classes
- scientific article; zbMATH DE number 719756 (Why is no real title available?)
- Adaptive logspace reducibility and parallel time
- The Helping Hierarchy
- 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02
- Computations with oracles that measure vanishing quantities
- The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
- A personal account of Turing's imprint on the development of computer science
- On sets bounded truth-table reducible to P-selective sets
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- On the Restraining Power of Guards
- The operators min and max on the polynomial hierarchy
- The complexity of generating test instances
- Some results concerning two-dimensional turing machines and finite automata
- On complexity classes and algorithmically random languages (extended abstract)
- Graph layout problems
- Degrees and reducibilities of easy tally sets
- Empty alternation
- Three forms of physical measurement and their computability
- Degrees of sets having no subsets of higher m- and t t-degree
- On the expressibility and the computability of untyped queries
- On pseudorandomness and resource-bounded measure
- Approximation of coNP sets by NP-complete sets
- Sets computable in polynomial time on average
- A recursion-theoretic approach to NP
- On the computational complexity of behavioral description-based web service composition
- Immunity and pseudorandomness of context-free languages
- Advocating ownership
- Theoretical computer science: computational complexity
- Zero-one laws and almost sure valuations of first-order logic in semiring semantics
- Nondeterministic, probabilistic and alternating computations on cellular array models
- Helping by unambiguous computation and probabilistic computation
- A weak version of the Blum, Shub, and Smale model
- Comparing nontriviality for E and EXP
- The complexity of achievement and maintenance problems in agent-based systems
- On the complexity of the two-variable guarded fragment with transitive guards
- Computational complexity of logical theories of one successor and another unary function
- A broader view on the limitations of information processing and communication by nature
- Reversal complexity revisited
- Fine hierarchies and m-reducibilities in theoretical computer science
- Structural properties of oracle classes
This page was built for publication: Structural complexity II
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3996675)