計算復(fù)雜性是計算復(fù)雜性領(lǐng)域的一個重要研究課題。其學(xué)科處于數(shù)學(xué)與理論計算機(jī)科學(xué)的結(jié)合點，具有清晰的數(shù)學(xué)輪廓和嚴(yán)格的數(shù)學(xué)格式。中心議題包括:計算模型、復(fù)雜性邊界(特別強(qiáng)調(diào)下界)、復(fù)雜性類、權(quán)衡結(jié)果用于順序和并行計算用于“一般”(布爾型)和“結(jié)構(gòu)化”計算(例如決策樹、算術(shù)電路)用于確定性、概率性和非確定性計算最壞情況和平均情況具體的集中領(lǐng)域包括:復(fù)雜性類的結(jié)構(gòu)(約簡、相對化問題、程度、去道德化)代數(shù)復(fù)雜度(雙線性復(fù)雜度，多項式、群、代數(shù)和表示的計算)交互證明、偽隨機(jī)生成和隨機(jī)抽取復(fù)雜性問題:學(xué)習(xí)理論數(shù)論邏輯(邏輯理論的復(fù)雜性，決策過程的成本)組合優(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