Theory of Computational Complexity

Theory of Computational Complexity
复制标题

DOI：
10.5860/choice.38-5623
复制
发表时间：
2000-01
期刊：
Genetics and molecular research : GMR
影响因子：
--
通讯作者：
D. Du;K. Ko
D. Du;K. Ko
中科院分区：
其他
文献类型：
--
作者：
D. Du;K. Ko

文献摘要

被引文献

相似文献

均匀的复杂性。计算和复杂性类的模型。 NP完整性。多项式时间层次结构和多项式空间。 NP的结构。不一致的复杂性。决策树。电路复杂性。多项式同构。概率复杂性。概率机器和复杂性类别。计数的复杂性。交互式证明系统。概率可检查的证明和NP-HARD优化问题。参考书目。指数。
UNIFORM COMPLEXITY. Models of Computation and Complexity Classes. NP-Completeness. The Polynomial-Time Hierarchy and Polynomial Space. Structure of NP. NONUNIFORM COMPLEXITY. Decision Trees. Circuit Complexity. Polynomial-Time Isomorphism. PROBABILISTIC COMPLEXITY. Probabilistic Machines and Complexity Classes. Complexity of Counting. Interactive Proof Systems. Probabilistically Checkable Proofs and NP-Hard Optimization Problems. Bibliography. Index.