Complexity theory retrospective II
Complexity theory retrospective II
复制标题
复杂性理论回顾二
DOI：
10.1007/978-1-4612-1872-2
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
A. Selman
中科院分区：
文献类型：
--
作者：
L. Hemaspaandra;A. Selman
1时间，硬件和均匀性。-1介绍。-2背景：描述性复杂性。-3第一个均匀性定理。-4比log nbits更长的变量。-5均匀性：第三维。 log nbits.- 7结论。-2量子计算。-1对量子力学的需求。-2量子力学的基本原理。-2.1概率振幅。-2.2 Qubits以及如何观察它们。-2.3量子密码学上的离题。-2.4量子系统的演变。-2.5量子寄存器。-3用量子寄存器计算。-4分隔两类函数。 6构建量子计算机。-3稀疏集与复杂性类别。 2.1稀疏集和多项式大小电路。 np.- 4.1扩展。-5 hartmanis猜想P.- 5.1 ogihara的语言-5.2确定性结构。-5.3结局：nc1模拟。-6结论。-4计数复杂性。-1介绍。-2预序列。-3计数函数。-3.1计数功能的代数属性。-3.2 a -3.3计数函数和多项式时间层次结构。-4计数类。-4.1分类计数class.- 4.2计数运算符。-4.3多项式时间层次结构.- 4.4 pp.- 5相对化的闭合属性。-6其他工作。-6.1电路。-6.1循环。-6.2 lowness.- 6.3表征特定问题。-6.4交互式证明系统.- 6.5在空间类中计数。-6.6其他研究。-5一个证明系统的分类学。证明系统。-2.2 MIP和PCP.- 2.3计算声明系统。-2.4其他类型的证明系统。-2.5比较。证明和程序检查。-3.4零知识证明。-6个指数时间的完整问题的结构属性。-1简介。-2强减少完整集。-3免疫力-4完整集合之间的4个差异。-5其他属性和开放问题。-5.1“弱”完整集的属性。-5.2多项式时间完整递归枚举集。-5.3一个开放问题的简短列表。-7获取NP和NL中问题解决方案的复杂性。独特的：NPSV.- 5级非自适应查询NP：fpnptt.-6 a内部的外观非确定logspace.- 7结论。-8生物计算。-1介绍。-1介绍。生物化学简介 - 3.1 DNA，RNA和蛋白质。-3.2蛋白质合成。-4计算分子-4.1 CNA.- 4.2 TCNA.- 4.3 TCNA的合成。-5 CNA计算机的微观结构。-6简短讨论Adleman的模型与我们的模型。 sublogarithmic空间类别是否有任何兴趣？-2交替的sublogarithmic空间世界。-3添加随机性。-4具有sublogarithmic空间绑定的机器的特殊限制。-4.1技术预定。-4.2具有周期性结构的输入。-4.3欺骗atms.- 5 dooms.- 5较低空间绑定的证明的调查 - 5.1 5.1语言，用于分开的水平交替层次结构。-5.2 ATM具有恒定数量交替的ATM。-5.3无界交替。-5.4闭合属性。 - 6个结论和开放问题。-10指数时间的定量结构。-1介绍。-2预先限制。-3个资源符合的措施。-4 4个不可压缩性和双重免疫性。-5个复杂性核心。 -6个小跨度定理。-7个虚弱的硬问题。-8的硬性问题上限。-9个不均匀的复杂性，自然证明和伪随机的发电机。- -11硬语言的密度。-12强假设。-13个结论和开放方向。-11个多项式和语言的多项式定义。-1简介。-1个多项式。 -5闭合特性的多项式上已知的上限和下限。-7概率-8其他组合结构。-12平均计算复杂性理论。-1介绍。-2平均多项式时间。-3平均案例完整性。-3.1多项式时降低。-3.2多项式计算分布。 3.3均匀分布。-3.4分布控制引理 - 3.5分布NP完整性。-3.6平均多项式时间减少。-3.7 -4随机分配搜索问题。-4.1平面分布和不完整。-4.2随机平均多项式时间。-4.3随机降低和完整性。-4.4多项式时间抽样。-4.5随机图灵降低。 .- 5.1平均时间层次结构。-5.2平均时间的快速收敛。-5.3平均分布排名。-6对其他结果的简要调查。
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.