论文标题
关于二阶布尔逻辑的角和克罗姆片段的复杂性
On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic
论文作者
论文摘要
二阶布尔逻辑是QBF的概括，其常数交替片段已知在指数时间层次结构的水平上是完整的。我们考虑了这种逻辑的两种限制类型：1）对术语结构的限制，2）限制布尔矩阵形式。在第一种类型中，我们考虑了两种限制：首先，不称呼适当函数变量的嵌套使用，其次规定每个函数变量必须以固定的参数序列出现。在第二种中，我们考虑了布尔矩阵的霍恩，克罗姆和核心碎片。我们通过结合这两种类型的限制来对获得的逻辑的复杂性进行分类。我们表明，在大多数情况下，具有k交替块量量化符的逻辑是针对指数时间层次结构的KTH或（K-1）级别的。此外，当k = 1时，我们为Krom和核心片段建立了NL的完整性，并且两种限制都是生效的。
Second-order Boolean logic is a generalization of QBF, whose constant alternation fragments are known to be complete for the levels of the exponential time hierarchy. We consider two types of restriction of this logic: 1) restrictions to term constructions, 2) restrictions to the form of the Boolean matrix. Of the first sort, we consider two kinds of restrictions: firstly, disallowing nested use of proper function variables, and secondly stipulating that each function variable must appear with a fixed sequence of arguments. Of the second sort, we consider Horn, Krom, and core fragments of the Boolean matrix. We classify the complexity of logics obtained by combining these two types of restrictions. We show that, in most cases, logics with k alternating blocks of function quantifiers are complete for the kth or (k-1)th level of the exponential time hierarchy. Furthermore, we establish NL-completeness for the Krom and core fragments, when k=1 and both restrictions of the first sort are in effect.
