空间复杂性是解决一个问题所需要消耗的空间资源的度量。与时间复杂性类似，空间复杂性也有 P 类和 NP 类，写作 PSAPCE 和 NPSPACE，也存在 NP 完全性现象。
萨维奇定理
萨维奇定理表明：尽管确定型图灵机需要指数级的时间开销才能模拟非确定型图灵机，但是确定型图灵机只需要非常少的空间开销就可以模拟非确定型图灵机。
这定理也从侧面表名，空间复杂性约束比时间复杂性约束更弱。也就是说，如果一个问题的空间复杂性是 P 级别的那么这个问题可能比多项式时间复杂度更困难。
这里有一个不严谨的关系推测：