指数空间下的多项式时间算法：是否属P类？P是否等于NP？

问题场景 #

假设我们找到了一种算法：它能在多项式时间内求解任意NP完全问题，但需要消耗指数级的空间。比如还原SHA256的例子——这个算法只需要256步，但编写它要用到2^256比特的空间。现在有两个核心问题：

1. 这种算法的时间复杂度属于P类吗？
2. 这是否意味着P=NP？

1. 该算法属于P类吗？ #

答案是肯定的，依据如下：
克雷数学研究所对P类的定义明确说明：

通俗来讲，P类是指可通过某种算法在输入长度的固定多项式步数内解决的决策问题类别。

这个定义只对时间复杂度做了多项式级的要求，完全没有限制空间的使用量。

再拿二叉决策树的例子类比：我们普遍认为深度为d的二叉决策树时间复杂度是O(d)，哪怕整个决策树的规模（空间占用）能达到2^d。这就说明，算法的时间复杂度评估和它需要的空间资源没有直接关联——只要时间满足多项式级，不管空间是多大，都符合P类的判定标准。

回到假设中的算法：它的时间是输入长度的多项式级（比如SHA256的例子里，256步是固定常数，属于O(1)，显然是多项式级），完全满足P类的定义，所以它属于P类。

2. 这是否意味着P=NP？ #

答案也是肯定的。
NP完全问题的核心性质是：所有NP类中的问题都可以在多项式时间内归约到任意一个NP完全问题。如果我们能找到一个多项式时间算法解决任意NP完全问题，那所有NP问题都可以通过归约，用这个算法在多项式时间内解决——这就意味着NP类被包含在P类中。

而我们早就知道P类是NP类的子集（所有能在多项式时间解决的问题，必然属于NP类），所以当NP包含于P、同时P包含于NP时，就可以得出P=NP的结论。

另外补充一点：虽然P类是PSPACE类的子集，而指数级空间属于EXPSPACE类（EXPSPACE包含PSPACE），但这完全不影响上述结论——因为P类的定义根本不限制空间，只要时间达标就行。

内容的提问来源于stack exchange，提问作者G S