描述复杂性

描述复杂性通过表达问题所需的逻辑的丰富性来刻画计算复杂性类，用逻辑可定义性取代了时间、空间等机器资源。

Definition

描述复杂性是有限模型理论的一个分支，它通过逻辑在有限结构上定义决策问题的方式对其进行分类，从而在复杂性类和逻辑语言之间建立精确的对应关系。

Scope

本主题涵盖了将NP与存在二阶逻辑等同起来的Fagin定理，通过不动点逻辑和传递闭包逻辑对P、NL和PSPACE的逻辑刻画，序和计数的作用，以及使用有限模型理论研究表达能力和解决复杂性类问题。

Core questions

• 计算难度能否通过逻辑表达能力而非机器资源来衡量？
• 哪种逻辑捕获了NP，哪种捕获了多项式时间？
• 为什么线性序的存在对这些刻画很重要？
• 逻辑方法如何有助于区分复杂性类？

Key theories

Fagin定理

有限结构的性质属于NP当且仅当它可以用存在二阶逻辑表达，这是该领域的奠基性成果，为主要的复杂性类提供了纯粹的逻辑的、独立于机器的刻画。

P和PSPACE的逻辑捕获

在有序结构上，多项式时间对应于带最小不动点算子的一阶逻辑，多项式空间对应于带部分不动点算子的一阶逻辑，将描述性程序扩展到整个复杂性层次结构中。

Clinical relevance

描述复杂性提供了一种独立于机器的可处理性解释，阐明了数据库查询语言的表达能力和效率，因为一阶逻辑和不动点逻辑对应于实用的查询语言。它还提供了逻辑工具，研究人员希望这些工具最终可能有助于区分复杂性类。

History

Fagin于1974年证明了他对NP的刻画，开创了该领域。Immerman和Vardi在大约1982年独立地通过有序结构上的不动点逻辑捕获了多项式时间，Immerman关于非确定性空间的工作，包括非确定性空间在补运算下的闭合性，进一步将逻辑与复杂性联系起来。

Debates

是否存在一种无需序就能捕获多项式时间的逻辑？

不动点逻辑只有在线性序可用时才能捕获P。是否存在某种逻辑能在无序结构上捕获多项式时间是一个核心的开放问题，因为否定的答案将区分P和NP，而肯定的答案将是一个重大进展。

Key figures

• Ronald Fagin
• Neil Immerman
• Moshe Vardi
• Bruno Courcelle

Seminal works

• immerman1999
• libkin2004

Frequently asked questions

用逻辑捕获复杂性类意味着什么？

这意味着该类中的问题恰好是那些可以通过逻辑公式在有限结构上表达的问题。例如，Fagin定理指出NP问题正是那些可以在存在二阶逻辑中定义的问题，因此类成员资格就变成了逻辑可表达性的问题。

描述复杂性为何关注排序？

有几种刻画，例如不动点逻辑捕获多项式时间，仅当结构带有逻辑可以使用的线性序时才成立。没有序，这些逻辑会变弱，而为多项式时间找到一种无序逻辑是一个与P与NP问题相关的深层开放问题。