satisfiability problem | BriefGPT

关键词satisfiability problem

搜索结果 - 12

IJCAI具有路径表达式的表达能力描述逻辑中的数据复杂度
探讨了在准林中非常表达性描述逻辑 ZOIQ (即 ALCHb Self reg OIQ) 上满足性问题的数据复杂性，并证明了它是 NP 完备的。这完成了对 ZOIQ 可判定片段的数据复杂性全景的研究，并重新证明了关于 OWL2 可判定片段（
PDF25 days ago
关于聚合组合图神经网络推理的逻辑
提出了一种模态逻辑，在其中计数模态出现在线性不等式中。将每个公式转换为等价的图神经网络（GNN）。证明了广泛类别的 GNN 可以高效地转换为公式，从而明显改进了关于 GNN 的逻辑表达能力的文献。证明了可满足性问题的 PSPACE 完备性。
PDF2 months ago
使用连续运行分布预测 SAT 局部搜索的并行加速
本文通过分析顺序版本算法的运行时行为，提出了一种评估给定算法并行性能的框架，并将此方法应用于研究两种 SAT 局部搜索求解器的并行性能，结果表明模型能够准确预测性能并展示了不同情况下局部搜索求解器的运行时分布。
PDF5 months ago
一种用于解释某些图神经网络的模态逻辑
该论文提出了一种包含线性不等式中计数模态的模态逻辑，证明了每个公式可以转化为等价的图神经网络（GNN），也证明了每个 GNN 可以转化为公式，说明可满足性问题是可判定的，并讨论了一些 PSPACE 内的变种。
PDFa year ago
学习可解释的 WalkSAT 启发式方法
使用强化学习来学习有效的变量评分函数和噪声参数，针对不同的实例分布学习专门的启发式方法，实验证明与基线方法以及另一个学习到的局部搜索启发式方法相比获得了改进。
PDFa year ago
SAT-Based 和 ASP-Based 算法在不一致性度量中的比较
本文研究了基于 SAT 求解和 ASP 的算法，用于解决确定命题知识库不一致度的问题，并考虑到六种不一致度测量标准。在广泛的实验分析中，我们将基于 SAT 和 ASP 的方法与一组基础算法进行比较，结果表明，在所有六种不一致度测量标准方面，
PDFa year ago
拓展可处理的多视角推理边界：一种适用于观点 EL+ 的演绎演算法
本文中，我们引入了一种称为 Standpoint EL + 的扩展逻辑，它允许公理否定、角色链公理、自我循环等特性，并且通过设计一个满足可实际算法需求的可满足性检查演绎规则，同时保持了可处理性。我们通过展示该演绎规则的一个原型 Datalo
PDFa year ago
探索 SLS 算法中长尾运行时间的理解
本论文研究了使用随机局部搜索解决基于满足性问题的 SAT 问题的流行范式，以及通过学习逻辑蕴含来改善求解器性能，并提出了一种生成逻辑等价问题形式的方法，进一步深入研究学习逻辑蕴含如何影响 SLS 运行时间的问题。
PDF2 years ago
计算 LTLf 规范的不可满足核心
本文提出四种算法用于提取 LTLf 规范中的不可满足核，并采用实验评估了各种算法和工具的可行性、有效性和互补性。
PDF2 years ago
关于动态认知逻辑的复杂性
本研究使用合法及完整的插入表技术，证明 DEL 语言中事件模型的模型检查问题是 PSPACE 完全的，并证明了满足性问题是 NEXPTIME-complete 的。
PDF11 years ago
FO (FD)：使用基于规则的不动点定义扩展经典逻辑
介绍了货值点定义 —— 一种基于规则的货值点重构。定义了 FO（FD）逻辑，它是一种扩展了经典逻辑的逻辑。探讨了 FO（FD）的可满足性问题。将 FO (FD) 简化为区别逻辑，然后使用区别逻辑求解器。在计算代表公平条件的 FO (FD)
PDF14 years ago
绝热演化量子计算
本文提出了一种基于绝热演化的量子算法，用于解决可满足性问题，其中 Hamiltonian 函数随时间变化，插入了初始 Hamiltonian 和最终 Hamiltonian，通过保证时间足够长，来确保系统演化到预期的最终基态，算法时间复杂度
PDF24 years ago