Expressibility as a Complexity Measure: Results and Directions
Expressibility as a Complexity Measure: Results and Directions
复制标题
作为复杂性衡量标准的表达性：结果和方向
DOI：
10.1109/psct.1987.10319271
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
N. Immerman
中科院分区：
文献类型：
--
作者：
N. Immerman
给定一个属性S，我们可以讨论检查输入是否满足S的计算复杂性。人们还可以问，"表达性质S的复杂性是什么？“这两个问题自然是相关的。然而，令人吃惊的是，当第二个问题涉及到用一阶逻辑表达该属性时，它们是多么紧密地联系在一起。在这篇文章中，我们调查了一些工作有关的一阶可表达的计算复杂性，并提出了一些开放的问题。大多数复杂性理论都是从图灵机或布尔电路的角度进行的。我们相信，一阶逻辑提供了一个有价值的不同的观点，增加了新的见解，充分研究的问题。
Given a property, S, one can discuss the computational complexity of checking whether or not an input satisfies S. One can also ask, "What is the complexity of expressing the property S?" It is natural that these two questions are related. However, it is startling how closely tied they are when the second question refers to expressing the property in first-order logic. In this article we survey some work relating first-order expressibility to computational complexity, and present a number of open problems. Most complexity theory is done from the point of view of Turing machines, or boolean circuits. We believe that first-order logic provides a valuable different point of view, adding fresh insights to well studied problems.