复杂度理论中某些不可证明的真命题

在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公