|
|||||
|
|
| 复杂度理论中某些不可证明的真命题 | |
| 引用本文： | 洪加威.复杂度理论中某些不可证明的真命题[J].科学通报,1983,28(5):316-316. |
| 作者姓名： | 洪加威 |
| 作者单位： | 北京工业大学第二分校 |
| 摘 要： | 在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到:复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如:“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果:定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公 |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《科学通报》浏览原始摘要信息 | |
| 点击此处可从《科学通报》下载免费的PDF全文 | |