描述复杂度（Descriptive Complexity）

描述复杂度是有限模型论的一个方向,它用逻辑可定义性来刻画计算复杂度类。其核心思想是:一个问题属于某复杂度类,当且仅当它能被某种特定逻辑所描述,从而把复杂度理论与逻辑表达能力等同起来。

概述

传统复杂度理论用图灵机和时间空间资源定义类别,而描述复杂度完全绕开机器模型。它把判定问题看成有限结构上的性质,再问需要多强的逻辑才能表达这一性质,资源的多寡由逻辑的丰富程度替代。

核心原理

• 法金定理是奠基结果,它证明NP恰好等于用存在二阶逻辑可表达的性质类。
• 在带有序关系的结构上,P对应于加了最小不动点算子的一阶逻辑。
• PSPACE对应于带偏序不动点或部分不动点的逻辑。
• 这种对应把机器无关性带入复杂度研究,使复杂度类获得纯逻辑的等价刻画。

应用场景

描述复杂度为复杂度类提供了机器无关的定义,便于比较不同类别的表达能力,也为数据库查询语言的能力划界。它启发人们通过研究逻辑而非机器来攻击复杂度分离问题,例如是否存在一种逻辑恰好捕获P一直是该领域的核心开放问题,其解答将深刻影响P与NP之争的走向与理解。

常见问题

问:法金定理具体说了什么?答:它断言一个有限结构上的性质属于NP,当且仅当它能用存在二阶逻辑表达,这是首个不提及机器就刻画复杂度类的结果,开创了整个描述复杂度领域。

问:为什么刻画P需要序关系?答:不动点逻辑在无序结构上无法数出元素或规定遍历顺序,因而表达力不足,加入内建的线性序后它才恰好等于P,这也是能否去掉序的深刻难题。