对算法复杂性的一种批评是它不符合我们对

常见语言复杂性的直觉。例如，当我们说某些东西很复杂时，

很少意味着一些随机的东西，但实际上这些东西不是微不足道的，

也不是随机的，而是相当复杂。字符串复杂性的度量，可以通过

组合算法信息内容和时间。

Charles Bennett(贝内特)介绍的深度，字符串的复杂性最好

由展开过程从其最短描述中重现字符串所花费的时间来定义。

花费的时间越长，越复杂。 复杂的对象是那些可以

作为“包含非平凡因果历史的内部证据”的对象。

与算法复杂度不同，算法复杂度将随机性分配给其最高复杂度值，

逻辑深度指定低的复杂度或低的深度给随机和琐细的对象。

因此它更符合我们对复杂物理对象的直觉，

因为琐碎和随机的对象直观易于生成，没有悠久的历史，

并且很快展开。

逻辑深度最初用通常认为是评估生物等

现实世界物体复杂性的正确标准来确定。

因此它的替代名称：物理复杂性（Bennett本人使用）。

这是因为逻辑深度的概念考虑了对象的合理历史。

它将对象的最短可能描述与此描述演变为其当前状态

所需的时间相结合。逻辑深度中的时间的

增加导致对对象的组织物理复杂性的合理表征

而单独使用算法复杂性的概念是不可能的。

Bennett本人提出了一个有说服力的案例，以便于逻辑深度的概念

作为衡量有组织的复杂性，超越和反对自身使用的算法复杂性。

贝内特的主要动机实际上是提供一种合理的方法来衡量现实

世界物体的物理复杂性。Bennett提供了逻辑深度概念

的仔细开发，考虑了最近的程序以及

最短的\ [Dash]因此显着性值\ [Dash]来达到一个相当稳健的度量。

要理解逻辑深度背后的直觉，请考虑以下几点。 想象一下，

一个随机文件,1000个位的大小：

如果您尝试压缩文件，则无法执行此操作：

例如，与压缩仅包含一千个1的文件相比。

现在，如果您测量压缩随机文件的解压缩时间：

你会发现它与压缩的简单文件的解压缩时

间没有什么不同：

这是因为两种情况下的解压缩指令都非常简单，

是因为文件很简单而另一种因为是因为几乎没有

随机文件的解压缩指令，因为我们无法压缩它。

但实际上你可以看到，在一个和另一个时间之间存在一个小的差异，

可能是因为随机文件确实有一些稍微复杂的解压缩步骤，

而不是完全无关紧要的情况。

但是现在让我们压缩一个既不简单也不随机的文件，看看会发生什么：

我们可以看到，就像我们预期的那样，通过算法生成并产生一些非平凡统计模式

的Thue-Morse序列可以比伪随机序列压缩更多位，但是通过小于普通文件，

它是 正如预期的那样处于中间位置，

并且解压缩时间也更长，因为现在解压缩指令比随机文件更多，

并且这些指令不像普通文件那么简单，

因此要更多的计算时间重现原始Thue-Morse序列。

这正是这个美丽的逻辑深度测量的核心思想。

从形式上，对于有限的字符串，Bennett的第一个逻辑深度测量定义如下。

设s为字符串，d为显着性水平。 字符串的深度由以下给出

公式:

在对象s的显着性水平较低的d处读取为大写字母D

的是在通用图灵机U上运行的计算机程序p所采用的最小时间T，

其可以再现s并且其程序长度与最短计算机程序p'相比较 .

1e不大于d，U（p）再现对象s。

因此算法复杂度和逻辑深度密切相关。

后者取决于前者，因为必须首先找到

产生字符串的最短程序，然后寻找最短的时间，

寻找最短的程序相当于近似字符串的算法复杂性。

虽然字符串的压缩版本是其算法复杂度的近似值，

但解压缩时间是该字符串的逻辑深度的近似值。

对于算法复杂性，通用图灵机的选择受到我们之前在讲座中

讨论的不变性定理的附加常数的限制，而对于逻辑深度，

所涉及的选择受乘法因子的限制，因此选择更重要但它们

仍然在某种程度上至少在理论上受控制。