Complexity Theory Retrospective II

This volume provides a survey of the subject in the form of a collection of articles written by experts, that together provides a comprehensive guide to research. The editors'aim has been to provide an accessible description of the current stae of complexity theory, and to demonstrate the breadth of techniques and results that make this subject so exciting. Thus, papers run the gamut from sublogarithmic space to exponential time, and from new combinatorial techniques to interactive proof systems.

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.- 2.1 Probability Amplitudes.- 2.2 Qubits and How to Observe Them.- 2.3 Digression on Quantum Cryptography.- 2.4 Evolution of a Quantum System.- 2.5 Quantum Registers.- 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.- 2.1 Sparse Sets and Polynomial Size Circuits.- 2.2 The Karp-Lipton Theorem.- 2.3 Long’s Extension.- 3 Earlier Results for Many-One Reductions.- 3.1 The Isomorphism Conjecture for NP.- 3.2 Mahaney’s Theorem.- 4 Bounded Truth Table Reduction of NP.- 4.1 Extensions.- 5 The Hartmanis Conjecture for P.- 5.1 Ogihara’s Language and Randomized NC2.- 5.2 Deterministic Construction.- 5.3 The Finale: NC1 Simulation.- 6 Conclusions.- 4 Counting Complexity.- 1 Introduction.- 2 Preliminaries.- 3 Counting Functions.- 3.1 Algebraic Properties of Counting Functions.- 3.2 A Randomized sign Function.- 3.3 Counting Functions and the Polynomial-Time Hierarchy.- 4 Counting Classes.- 4.1 Classifying Counting Classes.- 4.2 Counting Operators.- 4.3 The Polynomial-Time Hierarchy.- 4.4 Closure Properties of PP.- 5 Relativization.- 6 Other Work.- 6.1 Circuits.- 6.2 Lowness.- 6.3 Characterizing Specific Problems.- 6.4 Interactive Proof Systems.- 6.5 Counting in Space Classes.- 6.6 Other Research.- 5 A Taxonomy of Proof Systems.- 1 Introduction.- 2 A Technical Exposition.- 2.1 Interactive Proof Systems.- 2.2 MIP and PCP.- 2.3 Computationally Sound Proof Systems.- 2.4 Other Types of Proof Systems.- 2.5 Comparison.- 3 The Story.- 3.1 The Evolution of Proof Systems.- 3.2 PCP and Approximation.- 3.3 Interactive Proofs and Program Checking.- 3.4 Zero-Knowledge Proofs.- 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.- 5.1 Properties of “Weak” Complete Sets.- 5.2 Polynomial-Time Complete Recursively Enumerable Sets.- 5.3 A Short List of 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.- 3.1 DNA, RNA, and Proteins.- 3.2 Protein Synthesis.- 4 Computational Molecules.- 4.1 CNA.- 4.2 tCNA.- 4.3 The Synthesis of tCNA.- 5 The Microarchitecture of CNA Computers.- 6 A Brief Discussion of Adleman’s Model Versus Our Model.- 7 Conclusions.- 9 Computing with Sublogarithmic 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.- 4.1 Technical Preliminaries.- 4.2 Inputs with a Periodic Structure.- 4.3 Fooling ATMs.- 5 A Survey of Lower Space Bound Proofs.- 5.1 Languages for Separating the Levels of the Alternation Hierarchy.- 5.2 ATMs with a Constant Number of Alternations.- 5.3 Unbounded Alternation.- 5.4 Closure Properties.- 5.5 Lower Bounds for Context-Free Languages.- 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.- 3.1 Polynomial-Time Reductions.- 3.2 Polynomial-Time Computable Distributions.- 3.3 Uniform Distributions.- 3.4 Distribution Controlling Lemma.- 3.5 Distributional NP-Completeness.- 3.6 Average Polynomial-Time Reductions.- 3.7 Distributional Search Problems.- 4 Randomization.- 4.1 Flat Distributions and Incompleteness.- 4.2 Randomized Average Polynomial Time.- 4.3 Randomizing Reductions and Completeness.- 4.4 Polynomial-Time Sampling.- 4.5 Randomized Turing Reductions.- 5 Hierarchies of Average-Case Complexity.- 5.1 Average-Time Hierarchies.- 5.2 Fast Convergence of Average Time.- 5.3 Averaging on Ranking of Distributions.- 6 A Brief Survey of Other Results.