performance - 计算机科学的不确定性原理

Question

当我在做一个算法来解决一个计算问题时，我经常会体验到，使用更多的内存可以提高速度，而内存使用量可以以增加运行时间为代价，但我永远不能强求运行时间和消耗的内存低于明显明显的限制。这在形式上类似于海森堡的不确定性原理：位置不确定性与粒子动量不确定性的乘积不能小于给定阈值。

有没有一个计算机科学的定理，它断言同样的事情？我想应该可以从图灵机的理论中得出类似的东西。

Answer 1

我个人并不熟悉与海森堡不确定性原理本身相似的描述，但在我看来，这与计算复杂性理论密切相关。问题可以根据一些固有的、不可简化的复杂性进行分类，我认为这就是你对“运行时间和消耗内存的乘积”的限制。