带计数量词的双变量片段的数据复杂度
该研究将 Van den Broeck 等人关于加权第一阶模型计数在一阶逻辑中的多项式解法扩展到同时带有计数量词的两变量片段,探究其时间复杂度。
Jul, 2020
研究发现:在包含任意数量的传递关系的一元否定分段中,有限可满足性问题是可判定和 2-ExpTime 完全问题。此外,我们探讨了我们的基本逻辑的各种扩展的有限可满足性,特别是描述逻辑中已知的名称和角色层次概念的表达。
Sep, 2018
本文研究了有限结构中存在性正公式的答案数量计数问题,并在有界性条件下给出了关于查询类的三分定理,统一和泛化了关于合取查询和合取查询并的复杂性的已知结果。
Jan, 2016
本文研究了最近由 Wang 等人提出的一阶逻辑采样问题 —— 如何在有限域上高效地采样给定一阶句子的模型?我们将他们对于双变量逻辑 FO^2 的普遍量化子片段 UFO^2 的结果扩展到整个 FO^2 片段。具体来说,我们证明了 FO^2 在采样下的域可扩展性,即存在一种能在域大小多项式时间下运行的 FO^2 采样算法。然后,我们进一步表明,即使存在像所有 x 存在 = ky: φ(x,y)和存在 = kx 为所有 y 的数量约束,如 φ(x,y)的量化器公式,我们的方法也可以保持运作。我们的提出的方法是具有建设性的,由此产生的采样算法在各个领域都有潜在的应用,包括在组合结构和统计关系模型的均匀生成方面以及如 Markov 逻辑网络和概率逻辑程序的采样方面。
Feb, 2023
本研究将 van den Broeck 等人最近的对第二阶逻辑 FO2 下的对称加权一阶模型计数问题 (WFOMC) 多项式时间可解性证明,扩展到了两个独立方向:格式为 “phi 和∀∃^=1 psi” 的 FO2 句子以及在 FO 的一维均匀片段中构造的语句。同时,我们也鉴定了一阶前缀类的完整分类,以表明 WFOMC 在多项式时间或 Sharp-P_1 完备性之间的区别。
Apr, 2018
在平面图情况下,我们证明了与各种满足性、图形和组合问题相关的计数问题的 #P 难度。另外,当局限于计划实例时,我们证明了具有不明确解决方案性的满足性问题的 NP 完全性和与唯一满足性问题相关的随机多项式可简化的 DP 完全性。假设 P≠NP,则以上结果的一个推论是:不存在 ε- 逼近算法,用于在整数上计划线性不等式约束系统的最大化或最小化线性目标函数问题。
Sep, 1998
探讨了在准林中非常表达性描述逻辑 ZOIQ (即 ALCHb Self reg OIQ) 上满足性问题的数据复杂性,并证明了它是 NP 完备的。这完成了对 ZOIQ 可判定片段的数据复杂性全景的研究,并重新证明了关于 OWL2 可判定片段(SR 系列)的已知结果。利用相同的技术,我们证明了在 ZIQ 中带根查询的蕴涵问题在形式复杂度上是 coNEXPTIME 完备的。
Jun, 2024
本文研究了扩展时序约束问题的复杂性,并针对一组量词自由的 “小于等于(leq)” 公式所形成的 Poset-SAT 问题进行了讨论。其问题是对于 $x_1$,$x_2$,…,$x_n$ 成为偏序集时是否存在满足给定公式的赋值。最后,作者使用模型理论概念和通用代数技术研究了这些问题的约束满足问题,并提出了独立于通用代数和模型理论的分裂定理。
Feb, 2016
本文探讨了计算合取查询解的问题,考虑了公式的量化星级大小对于计算问题的可处理性的影响,并在有限的情况下确定了可计数的解的限制条件,介绍了量化星级大小的计算方法及其在多种宽度计算中的适用性,最后在输入宽度的多项式时间内提供了量化星级大小的近似计算。
Mar, 2013