COMPUTATIONAL COMPLEXITY

计算复杂性是计算复杂性领域的一个重要研究课题。其学科处于数学与理论计算机科学的结合点，具有清晰的数学轮廓和严格的数学格式。中心议题包括:计算模型、复杂性边界(特别强调下界)、复杂性类、权衡结果用于顺序和并行计算用于“一般”(布尔型)和“结构化”计算(例如决策树、算术电路)用于确定性、概率性和非确定性计算最坏情况和平均情况具体的集中领域包括:复杂性类的结构(约简、相对化问题、程度、去道德化)代数复杂度(双线性复杂度，多项式、群、代数和表示的计算)交互证明、伪随机生成和随机抽取复杂性问题:学习理论数论逻辑(逻辑理论的复杂性，决策过程的成本)组合优化和近似解分布式计算性能测试

computational complexity presents outstanding research in computational complexity. Its subject is at the interface between mathematics and theoretical computer science, with a clear mathematical profile and strictly mathematical format.The central topics are:Models of computation, complexity bounds (with particular emphasis on lower bounds), complexity classes, trade-off resultsfor sequential and parallel computationfor "general" (Boolean) and "structured" computation (e.g. decision trees, arithmetic circuits)for deterministic, probabilistic, and nondeterministic computationworst case and average caseSpecific areas of concentration include:Structure of complexity classes (reductions, relativization questions, degrees, derandomization)Algebraic complexity (bilinear complexity, computations for polynomials, groups, algebras, and representations)Interactive proofs, pseudorandom generation, and randomness extractionComplexity issues in:learning theorynumber theorylogic (complexity of logical theories, cost of decision procedures)combinatorial optimization and approximate Solutionsdistributed computingproperty testing