Nov, 2008

命题蕴涵的复杂性

PDF
TL;DR本研究考察了基于一组有限的布尔连结词所建立的命题公式的子句集合 G 是否蕴含某个公式 f 的复杂性，并证明了只有当连结词可由 {false，true} 和 {and，or，xor} 定义时，蕴含问题才能有效求解，此时问题的复杂度为多项式级别，否则问题的复杂度仍然是 coNP 完备的，并且还考虑了 G 被限制为单元素的情况。
propositional formulaeboolean connectivescomplexity classificationimplication problempost's lattice
发现论文，激发创造
  • 一种基于存在图的系统命题公式简化框架

    本文介绍了一种基于 Peirce 的存在图推理和蕴含图的命题逻辑简化演算法，该算法可以应用于嵌套形式的命题逻辑公式，保持等价性、保证变量、子句和文字数量的单调递减，并最大限度地保留结构问题信息；同时，提出了一个系统化应用两个规则（EPR 和 TWSR）的简化过程，可用于简化大型布尔可满足性问题和任意形式的命题公式，并对其在空间和时间方面进行了算法复杂性的形式分析；最后，展示了如何通过引入一种新的 n 元蕴含图扩展我们的规则，以涵盖所有已知的等价性保持预处理过程。

    May, 2024

  • 可解释性通过短公式：命题逻辑的案例与实现

    该研究旨在通过定义解释性、逻辑和公式大小来解决特定的解释问题，对命题逻辑进行了研究，最终提供了与 n 皇后和支配集问题相关的问题解释能力的实现。

    Sep, 2022

  • (1+1) 遗传规划使用功能完备指令集可以演化出任意小误差的布尔与和或

    使用 GP 系统和完全函数集可以高效地求解 n 个变量的布尔合取或析取问题，同时引入了超乘积漂移定理以给出更强的运行时间上限。

    Mar, 2023

  • 关于概率和因果推理的困难程度

    研究员从计算复杂性的角度出发，研究了能够完全表达数量化概率推理和因果效应的形式语言。研究集中于可表达许多概率和因果推断任务的可满足性问题，并建立了这些可满足性问题的确切计算复杂性。研究结果表明，一些在概率和因果推断中常用的标准语言的变体的算法限制更强。

    May, 2023

  • 布尔函数综合的知识编译

    研究 Boolean functional synthesis 问题中 CNF 转化为 SynNNF 的算法，并证明 SynNNF 具有多项式时间综合的优势。

    Aug, 2019

  • 概率和因果可满足性：边缘化的影响

    研究了 Pearl 的因果层次结构 (PCH) 框架中的推理和计算复杂性，重点关注概率和因果语言中表达的满足性问题，特别是与边缘化相关的方程，证明了不同层次和操作符的确切计算复杂性结果，以及对受限模型进行了考虑。

    May, 2024

  • 电路复杂度和全局约束的分解

    使用电路复杂度工具研究全局约束的分解，证明约束传播器存在一个多项式大小分解，当且仅当可以通过一个多项式大小单调布尔电路计算，并证明领域一致性传播者不存在多项式大小分解。

    May, 2009

  • 具有传递性的一元否定片段的有限可满足性

    研究发现：在包含任意数量的传递关系的一元否定分段中，有限可满足性问题是可判定和 2-ExpTime 完全问题。此外，我们探讨了我们的基本逻辑的各种扩展的有限可满足性，特别是描述逻辑中已知的名称和角色层次概念的表达。

    Sep, 2018

  • 算法信息论的电路复杂度表述

    研究基于电路复杂度的先验模型，并使用它们来学习部分信息中的布尔函数。该模型假设，布尔函数或布尔字符串由一些电路的贝叶斯混合生成。在电路复杂度方面表现良好。

    Jun, 2023

  • 偏序约束满足问题的复杂性二分定理

    本文研究了扩展时序约束问题的复杂性，并针对一组量词自由的 “小于等于（leq）” 公式所形成的 Poset-SAT 问题进行了讨论。其问题是对于 $x_1$，$x_2$，…，$x_n$ 成为偏序集时是否存在满足给定公式的赋值。最后，作者使用模型理论概念和通用代数技术研究了这些问题的约束满足问题，并提出了独立于通用代数和模型理论的分裂定理。

    Feb, 2016