| 关于NP完全问题的多项式线路可判定性 |
| |
| 引用本文： | 吕义忠,孙慧澄.关于NP完全问题的多项式线路可判定性[J].南京航空航天大学学报,1996,28(5):621-625. |
| |
| 作者姓名： | 吕义忠 孙慧澄 |
| |
| 作者单位： | 南京航空航天大学计算机科学与工程系(吕义忠)，南京大学数学系(孙慧澄) |
| |
| 基金项目： | 国家自然科学基金,863国家高技术研究发展计划资助 |
| |
| 摘 要： | 在计算复杂性领域里，大多数复杂类都是按照接受它们的图灵机而加以描述的。８０年代初，人们广泛关注被多项式大小的线路可判定的集合类并且得到了许多有趣的结果。但是，迄今是否ＮＰ完全问题是多项式大小的线路可判定的问题仍然是开的。最好的结果是，如果答案是肯定的，则多项式时间的分层便塌方到２级，即，ＰＨ＝Σ２。本文考虑一个特殊的无穷图的集合和讨论它被多项式大小线路逼近接受的问题，且利用紧致性定理和常数扩张法证明了存在集合Ａ∈ＣＯ－ＮＰ＼Ｐ／ｐｏｌｙ。
|
| 关 键 词： | 理论计算机科学 数据逻辑 计算复杂性 图灵机 多项式大小的布尔线路族 |
On Decidability of NP Complete Problems by Polynomial Sized Circuit |
| |
| L Yizhong.On Decidability of NP Complete Problems by Polynomial Sized Circuit[J].Journal of Nanjing University of Aeronautics & Astronautics,1996,28(5):621-625. |
| |
| Authors: | L Yizhong |
| |
| Abstract: | |
| |
| Keywords: | theoretical computer science mathematical logic computational complexity Turing machine polynomial sized circuit |
| 本文献已被 CNKI 维普 等数据库收录！ |
