Progress in Computational Complexity Theory
摘要
We briefly survey a number of important recent achievements 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.
引用本文（GB/T 7714）
蔡进一, 朱洪. Progress in Computational Complexity Theory[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2005.
引文网络
本站仅收录题录与摘要供学习参考，全文版权归属出版方；如有侵权请联系我们删除。