期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
Progress in Computational Complexity Theory
1
作者 蔡进一 朱洪 《Journal of Computer Science & Technology》 SCIE EI CSCD 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 o... 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
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部