| 用结构性质分开复杂类 |
| |
| 引用本文： | 吕义忠.用结构性质分开复杂类[J].计算机研究与发展,1999,24(8):932-935. |
| |
| 作者姓名： | 吕义忠 |
| |
| 作者单位： | 南京航空航天大学计算机科学与工程系,南京,210016;南京大学计算机软件新技术国家重点实验室,南京,210093 |
| |
| 摘 要： | ＮＰ是否包含在Ｐ／ｐｏｌｙ中的问题迄今仍为开问题。８０年代初证明了如果ＮＰ∪→Ｐ／ｐｌｙ，则ＰＨ＝∑２，最近，又有了如果ＮＰ∪→Ｐ／ｐｏｌｙ，则ＰＨ＝ＺＰＰ的问题。文中将借助于广义一阶逻辑ζ（ι）及其上的模型论以证明存在ＮＰ中的语言，它们没有多项式大小的线路。
|
| 关 键 词： | 结构复杂性 广义一阶逻辑 图论 |
SEPARATING COMPLEXITY CLASSES BY THEIR STRUCTURAL PROPERTIES |
| |
| Lü Yi-Zhong.SEPARATING COMPLEXITY CLASSES BY THEIR STRUCTURAL PROPERTIES[J].Journal of Computer Research and Development,1999,24(8):932-935. |
| |
| Authors: | Lü Yi-Zhong |
| |
| Abstract: | |
| |
| Keywords: | structural complexity extended first order logic graph theory |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
