Complexity Theory Retrospective II

This volume provides a comprehensive survey of the current state of research in complexity theory. It comprises a series of authoritative articles written by experts in their respective fields, and has been carefully edited to ensure a uniformity of notation and level of treatment. Researchers in computer science and mathematics will find much of interest here.

Inhalt
1 Time, Hardware, and Uniformity.- 1 Introduction.- 2 Background: Descriptive Complexity.- 3 First Uniformity Theorem.- 4 Variables That Are Longer Than log nBits.- 5 Uniformity: The Third Dimension.- 6 Variables That Are Shorter Than log nBits.- 7 Conclusions.- 2 Quantum Computation.- 1 The Need for Quantum Mechanics.- 2 Basic Principles of Quantum Mechanics.- 3 Computing with Quantum Registers.- 4 Separating Two Classes of Functions.- 5 Shor's Factoring Algorithm.- 6 Building a Quantum Computer.- 3 Sparse Sets versus Complexity Classes.- 1 Introduction.- 2 Earlier Results for Turing Reductions.- 3 Earlier Results for Many-One Reductions.- 4 Bounded Truth Table Reduction of NP.- 5 The Hartmanis Conjecture for P.- 6 Conclusions.- 4 Counting Complexity.- 1 Introduction.- 2 Preliminaries.- 3 Counting Functions.- 4 Counting Classes.- 5 Relativization.- 6 Other Work.- 5 A Taxonomy of Proof Systems.- 1 Introduction.- 2 A Technical Exposition.- 3 The Story.- 6 Structural Properties of Complete Problems for Exponential Time.- 1 Introduction.- 2 Strong Reductions to Complete Sets.- 3 Immunity for Complete Problems.- 4 Differences between Complete Sets.- 5 Other Properties and Open Problems.- 7 The Complexity of Obtaining Solutions for Problems in NP and NL.- 1 Introduction.- 2 Computing Optimal Solutions: The Class FPNP.- 3 Bounded Queries to NP.- 4 Computing Solutions Uniquely: The Class NPSV.- 5 Nonadaptive Queries to NP: The Class FPNPtt.- 6 A Look inside Nondeterministic Logspace.- 7 Conclusions.- 8 Biological Computing.- 1 Introduction.- 2 The One-Molecule Processor.- 3 A Brief Introduction to Biochemistry.- 4 Computational Molecules.- 5 The Microarchitecture of CNA Computers.- 6 A Brief Discussion of Adleman's Model Versus Our Model.- 7 Conclusions.- 9 Computing withSublogarithmic Space.- 1 Are Sublogarithmic Space Classes of Any Interest?.- 2 The Alternating Sublogarithmic Space World.- 3 Adding Randomness.- 4 Special Limitations of Machines with a Sublogarithmic Space Bound.- 5 A Survey of Lower Space Bound Proofs.- 6 Conclusions and Open Problems.- 10 The Quantitative Structure of Exponential Time.- 1 Introduction.- 2 Preliminaries.- 3 Resource-Bounded Measure.- 4 Incompressibility and Bi-Immunity.- 5 Complexity Cores.- 6 Small Span Theorems.- 7 Weakly Hard Problems.- 8 Upper Bounds for Hard Problems.- 9 Nonuniform Complexity, Natural Proofs, and Pseudorandom Generators.- 10 Weak Stochasticity.- 11 Density of Hard Languages.- 12 Strong Hypotheses.- 13 Conclusions and Open Directions.- 11 Polynomials and Combinatorial Definitions of Languages.- 1 Introduction.- 2 Polynomials.- 3 Representation Schemes and Language Classes.- 4 Strong versus Weak Representation.- 5 Known Upper and Lower Bounds on Degree.- 6 Polynomials for Closure Properties.- 7 Probabilistic Polynomials.- 8 Other Combinatorial Structures.- 12 Average-Case Computational Complexity Theory.- 1 Introduction.- 2 Average Polynomial Time.- 3 Average-Case Completeness.- 4 Randomization.- 5 Hierarchies of Average-Case Complexity.- 6 A Brief Survey of Other Results.