通过分析具有值约束的表达能力以及函数的某些代数性质,我们否定了一个开放问题,即是否所有的布尔子模函数都可以分解成可能更大的一组变量上的二元子模函数之和,并确定了这种约束的一些限制。
Nov, 2008
使用电路复杂度工具研究全局约束的分解,证明约束传播器存在一个多项式大小分解,当且仅当可以通过一个多项式大小单调布尔电路计算,并证明领域一致性传播者不存在多项式大小分解。
May, 2009
本文研究表明,像ALL-DIFFERENT和GCC等一些常见且重要的全局约束可以被分解为简单的算术约束,我们可以在这些约束上实现界限或范围一致性,甚至可以进行更大的削减。我们在一个伪布尔求解器中使用这些分解进行了实验。
研究使用一个特殊的集合来使得一类复杂计算问题变得简单化的方法,利用该方法可以实现CNF公式求解的多项式时间算法,同时该研究提出了一些关于求解backdoor sets大小和检测方法的结论。
Oct, 2011
本文结合分解性和后门集两种方法,研究了在与给定CNF公式相关联的图的树宽不超过t的CNF公式集合W_t中找到一个小的强后门集的算法问题。我们证明了:1.找到大小不超过2^k的强W_t后门集,或确定F没有大小不超过k的强W_t后门集;2.找到CNF公式F的满足分配数量或确定sb_t(F)> k的算法,其中sb_t(F)表示F的最小强W_t后门集的大小。
Apr, 2012
该研究论文介绍了 DR-submodular 函数以及其最大化问题,给出了从 DR-submodular 方程到 submodular 方程的通用约简方式,并将前者的结果转化为后者,使其适用于许多类型的限制约束。
Jun, 2016
本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法,研究人工智能领域的几个已知问题,其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性,但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。
May, 2018
提出一种基于代数结构的算法来计算具有最大价值最佳解的 DNNF 电路中的 k 个最优模型,并且 与 基于部分加权 MaxSAT 求解器的算法进行比较。
Feb, 2022
对称矩阵的“非返环”矩阵的定义和“Ihara-Bass”类型公式的证明,用于证明具有k个变量的约束满足问题(k-CSP)的多项式时间强驳斥结果,同时提出了新的结果。
Apr, 2022
本文研究打击公式的可满足性和分辨率复杂性,确定不可化简打击公式来确定其分辨率复杂性,并使用 Nauty 软件包枚举其精确的分辨率复杂性等。
Jun, 2022