论文标题
关于量词的数量作为复杂度度量
On the Number of Quantifiers as a Complexity Measure
论文作者
论文摘要
1981年，尼尔·内曼（Neil Immerman）描述了一个两人游戏，他称之为“可分离性游戏” \ cite {inmerman81}，该游戏捕获了描述一阶逻辑中属性所需的量化器数量。 Immerman的论文为研究表达一阶逻辑表达属性所需的量化数的数量奠定了基础，但是该游戏似乎太复杂了，无法研究，并且本文的论点几乎仅用量化器排名作为量化量总数的下限。但是，去年Fagin，Lenchner，Regan和Vyas重新发现了游戏，提供了一些用于分析它们的工具，并展示了如何利用它们来表征表达不同大小的线性订单所需的量化数量。在本文中，我们通过建立几个新结果来研究量词数量作为真正的复杂性度量。首先，我们仔细地将最小数量的量词与更常见的描述复杂度度量，最小量词等级和最小变量数。然后，对于每个正整数$ k $，我们给出一个有限结构（尤其是有限图的属性）的明确示例，可以用量词等级$ k $表示，但是同一属性需要$ 2^{ω（k^2）} $量词来表达。
In 1981, Neil Immerman described a two-player game, which he called the "separability game" \cite{Immerman81}, that captures the number of quantifiers needed to describe a property in first-order logic. Immerman's paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas rediscovered the games, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer $k$, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank $k$, but where the same property needs $2^{Ω(k^2)}$ quantifiers to be expressed.
