Structural complexity. I
bibliographycircuit complexitycomplete problemscomplexity classescomplexity theorydiagonalizationP-NP-problempolynomial time hierarchyProbabilistic algorithmsstructural complexitystructural propertiesTuring machines
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25)
This is the first volume of a two volume textbook on a structurally oriented approach to complexity theory. Complexity theory is dealing with ressource-bounded universal computing devices, typically Turing machines. Structural complexity is interested in any interrelationship between complexity classes which is beyond the pure ``quantitative point of view. Many results in structural complexity theory are influenced by, or have their origin in, recursive function theory. The field has maturated in the last years and the present book is the first that summarizes and unifies many different contributions published up to now only in journal articles and conference proceedings. After introducing the basic notions and computational models, discussing boundedness in resources such as time and space, many central structural issues are then presented in Chapters 3 and 4: reducibilities, completeness, honesty and invertibility of functions, paddability and self-reducibility of languages, and sparseness. Chapter 5 introduces the concept of Boolean circuit (or nonuniform) complexity and compares it with the (uniform) notions discussed so far. The connection can be drawn via Karp and Lipton's ``advice notion. Probabilistic algorithms (and corresponding complexity classes) are the theme of Chapter 6. Such algorithms have achieved much attention in the last years. An interesting relation between probabilistic classes and the nonuniform classes from Chapter 5 is revealed in Section 6.5. A uniform diagonalization method is then introduced in Chapter 7 which allows to obtain certain languages with ``intermediate properties. Finally, Chapter 8 finishes the book with a discussion of the polynomial time hierarchy - an analogue of Kleene's arithmetical hierarchy - and again, another interesting link to the probabilistic classes is drawn in Section 8.5. The book contains many exercises, both straightforward ones and some of a research project level. In most parts of the book the reader is led up to the current state of the art in research in the field. The list of references contains about 150 entries, so that every interested reader is invited (and gets a very good basis) for proceeding with his own research in the field.
- Complexity and structure
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Bounded queries to SAT and the Boolean hierarchy
- On random oracle separations
- On p-creative sets and p-completely creative sets
- Almost everywhere high nonuniform complexity
- A survey of space complexity
- On polynomial-time Turing and many-one completeness in PSPACE
- A note on two-way probabilistic automata
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Complexity of logical theories involving coprimality
- Deciding bisimilarity is P-complete
- On the computational complexity of integral equations
- Unambiguity of circuits
- Circuit size relative to pseudorandom oracles
- On 1-truth-table-hard languages
- A positive relativization of polynomial time versus polylog space
- A note on sparse sets and the polynomial-time hierarchy
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Saturation and stability in the theory of computation over the reals
- The alternation hierarchy for sublogarithmic space is infinite
- A modal perspective on the computational complexity of attribute value grammar
- A note on SpanP functions
- One-way functions and the isomorphism conjecture
- Simple characterizations of \(P(\# P)\) and complete problems
- Computational depth and reducibility
- A note on the density of oracle decreasing time-space complexity
- Listing graphs that satisfy first-order sentences
- Finite-valued distance automata
- On the computational power of dynamical systems and hybrid systems
- The simple dynamics of super Turing theories
- On resource-bounded instance complexity
- An excursion to the Kolmogorov random strings
- Counting quantifiers, successor relations, and logarithmic space
- A reducibility concept for problems defined in terms of ordered binary decision diagrams
- Index sets and presentations of complexity classes
- Gap-languages and log-time complexity classes
- An oracle builder's toolkit
- Optimal proof systems imply complete sets for promise classes
- Test sets for the universal and existential closure of regular tree languages.
- On the simulation of quantum Turing machines.
- Resource bounded randomness and computational complexity
- Undecidability results for low complexity time classes
- Exact learning via teaching assistants
- The counting complexity of group-definable languages
- Stochastic analog networks and computational complexity
- Transfer theorems via sign conditions
- On the computational structure of the connected components of a hard problem
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- Multi-head finite automata: Data-independent versus data-dependent computations
- Sparse selfreducible sets and nonuniform lower bounds
- TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
- The price of universality
- On the Hamming distance of constraint satisfaction problems.
- Deterministic Turing machines in the range between real-time and linear-time.
- One complexity theorist's view of quantum computing
- Alternating and empty alternating auxiliary stack automata.
- Assembling molecules in ATOMIX is hard
- Nonuniform lowness and strong nonuniform lowness
- Toughness, hamiltonicity and split graphs
- On the geometric separability of Boolean functions
- Entanglement and the complexity of directed graphs
- Non-uniform reductions
- Max NP-completeness made easy
- Two queries
- A bounded arithmetic AID for Frege systems
- \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration
- Bounded truth table does not reduce the one-query tautologies to a random oracle
- Polynomial recognition of equal unions in hypergraphs with few vertices of large degree
- Model checking abilities of agents: a closer look
- Combined hierarchies of finite random access machines
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Graph Isomorphism is in SPP
- How much can analog and hybrid systems be proved (super-)Turing
- Sets without subsets of higher many-one degree
- A common algebraic description for probabilistic and quantum computations
- A reducibility for the dot-depth hierarchy
- A note on the circuit complexity of PP
- On approximate learning by multi-layered feedforward circuits
- On the typical case complexity of graph optimization
- Machines that perform measurements
- The complexity of searching implicit graphs
- A characterization of the leaf language classes
- Coloring Jacobians revisited: a new algorithm for star and acyclic bicoloring
- Sparse sets, approximable sets, and parallel queries to NP
- Classes of bounded nondeterminism
- Limits to measurement in experiments governed by algorithms
- Axiomatizing resource bounds for measure
- Complexity issues for preorders on finite labeled forests
- On the complexity of Szilard languages of regulated grammars
- Do there exist complete sets for promise classes?
- Self-reducible sets of small density
- Reducibilities on tally and sparse sets
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- Limitations of the upward separation technique
- scientific article; zbMATH DE number 4166857 (Why is no real title available?)
- On the Complexity of Measurement in Classical Physics
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- A Characterisation of NL Using Membrane Systems without Charges and Dissolution
- Extending regular expressions with homomorphic replacement
This page was built for publication: Structural complexity. I
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4039803)
