SEP：可计算性与复杂性（二） (5-5)

关于这种完全性现象的原因并没有得到充分的解释。一个可信的解释是，自然计算问题(natural computational problems)往往是通用的(译注：或作普遍的，下同)，在图灵的通用机的意义上。而关于某个既定复杂性类的，一个通用问题，可以模拟该类中任何其他问题。而NP类被如此广泛研究的原因则是，大量且重要的实际问题都是对于NP完全的，包括子集和问题。而其中没一个被已知，存在一个算法，其可以快于指数级的时间去解决它们，尽管一些NP完全问题允许关于它们的近似可行解。

关于计算复杂性的大量的问题都还是开放的。我们知道，严格地说，更多的计算资源(computational resources)，可使得我们解决，严格上更难的问题，例如TlME[n]真包含于TlME[n¹.01]中，相似地，对于SPACE ，以及其他量度来说同样如此。然而，在不同计算资源间的权衡上，我们的理解仍然十分贫乏。显然，P被包含于NP中。进一步，NP被包含在PSPACE中，因为在PSPACE中，我们可以系统性地尝试NP计算的每一个分支，对连续的分支再利用空间，并且接受它，当且仅当这些分支中的任何一个导向了接受。PSPACE被包含在EXPTlME中，因为，当一个PSPACE机要花超过指数级的时间时，那么它就确切地重复了一些配置，所以它也一定是在无限循环。以下是关于上面这些类的已知关系

P ⊆ NP ⊆ PSPACE ⊆ EXPTlME

然而，尽管看上去很清楚地，P真包含于NP，而NP真包含于PSPACE，PSPACE也真包含于EXPTIME，但其中任何这些类的不等关系都没有得到过证明。实际上，甚至对于P是否不同于PSPACE，或者NP是否不同于EXPTIME，我们都是不知道的。从上面可知，真包含关系只有，P真包含于EXPTIME。余下的问题，涉及到不同计算资源的相对效力，而这是个计算理论中的基础性的未解难题。

关于计算复杂性有一个广泛的理论，本条目只简单描述了这一领域，将其置于在了，什么是原则上与实践上可计算的，这个问题的语境下。对于那些有志于学习更多关于复杂性的读者有很多非常不错的著作，比如[Papadimitriou, 1994]，与[Arora and Barak, 2009]，以及同样有条目Computational Complexity Theory。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。