中文簡(jiǎn)介

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

英文簡(jiǎn)介

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