中文簡介

計算復雜性是計算復雜性領域的一個重要研究課題。其學科處于數(shù)學與理論計算機科學的結合點，具有清晰的數(shù)學輪廓和嚴格的數(shù)學格式。中心議題包括:計算模型、復雜性邊界(特別強調下界)、復雜性類、權衡結果用于順序和并行計算用于“一般”(布爾型)和“結構化”計算(例如決策樹、算術電路)用于確定性、概率性和非確定性計算最壞情況和平均情況具體的集中領域包括:復雜性類的結構(約簡、相對化問題、程度、去道德化)代數(shù)復雜度(雙線性復雜度，多項式、群、代數(shù)和表示的計算)交互證明、偽隨機生成和隨機抽取復雜性問題:學習理論數(shù)論邏輯(邏輯理論的復雜性，決策過程的成本)組合優(yōu)化和近似解分布式計算性能測試

英文簡介

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