Progress in Computational Complexity Theory  

作　　者：蔡进一 朱洪 

机构地区：[1]Computer Sciences Department, University of Wisconsin, Madison, WI 53706, U.S.A. [2]Tsinghua University, Beijing 100084, P.R. China [3]Computer Sciences Department, Fudan University, Shanghai 200333, P.R. China

出　　处：《Journal of Computer Science & Technology》2005年第6期735-750,共16页计算机科学技术学报（英文版）

基　　金：美国自然科学基金，国家自然科学基金

摘　　要：We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant＇s new theory of holographic algorithms and reductions.We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant＇s new theory of holographic algorithms and reductions.

关 键 词：theoretical computer science computational complexity theory PCP theorem INAPPROXIMABILITY logspace complexity Reingold＇s theorem GAP problem primality testing complexity of lattice problems worst-case to average-case reductions PSEUDORANDOMNESS EXTRACTORS holographic algorithms 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]