%0 Journal Article
%T 复杂度理论中某些不可证明的真命题
%A 洪加威
%J 科学通报
%D 1983
%I 
%X 在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到:复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如:“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果:定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=7C7E63796F062382A606A3A9833B8C05&jid=B40D4BA57FF46E45205A09B4DC283152&aid=F52DEBAB7E3DA0BFEA1F660FD38DC9F2&yid=A7F20A391020FDEE&vid=D3E34374A0D77D7F&iid=94C357A881DFC066&sid=EC34D52BE81085CE&eid=EC34D52BE81085CE&journal_id=0023-074X&journal_name=科学通报&referenced_num=0&reference_num=0