无限域约束满足问题中的计算捷径
本文对基于约束满足问题的多项式算法强后门检测问题进行了系统研究,特别是当目标属性是由多项式函数族定义的特定约束语言时,我们表明在多项式函数族是幂等的假设下,当参数为 r(约束元数)或 k(后门大小)时,问题不可能是 FPT,除非 P = NP 或 FPT = W [2]。但是当参数为 k + r 时,我们能够识别出大量语言,以便找到小后门的问题是 FPT。
Apr, 2014
本研究论文表明,当以任何可转化为有限约束语言的可解 CSP 问题作为背景门限时,CSP 是固定参数可解的,这将结合了两个解决 CSP 可解性问题的突出方法:(i) 通过变量和约束之间交互的结构限制和 (ii) 通过内部约束所使用的关系的语言限制。除了定义背景门限的概念并展示如何利用小的背景门限来高效求解 CSP 之外,本文主要技术贡献是提出了一种寻找小背景门限的固定参数算法。
Oct, 2016
本文介绍了一个算法,用于找到具有给定列表中的类中的离散类的强后门,这些类由 CSP 实例中的连通分量确定,并表明满足特定条件时,可以通过这种方式超越 CSP 的易处理性限制。
Jul, 2015
研究了约束满足问题中基本关系具有小拼接性质的 CSP,提出了一种求解这类问题的算法,时间复杂度为 f (w)・n^{O (1)},并且不仅限于二元约束。
Jul, 2021
研究使用一个特殊的集合来使得一类复杂计算问题变得简单化的方法,利用该方法可以实现 CNF 公式求解的多项式时间算法,同时该研究提出了一些关于求解 backdoor sets 大小和检测方法的结论。
Oct, 2011
提出了一种基于 Monte Carlo Tree Search- BaMCTS 算法,在 Mixed Integer Linear Programming(MIP)中通过构建 backdoor(后门) 数据集来提高 MIP 问题的求解效率。该算法与传统 MIP 概念相结合,且与 CPLEX 求解器紧密集成,成功地优化了 MIPLIB2017 示例的求解效率。
Oct, 2021
本文提出一种新的 SAT 后门集类别,用于密码攻击中的猜测和确定攻击,通过使用 SAT 求解器识别最佳的后门变量集以及统计预估硬度,实验结果显示该方法较现有技术在反推攻击的硬度方面具有优势。
Mar, 2018
本文介绍了如何使用 backdoors 的概念来识别能够使 ASP 问题可行的新限制,展示了 backdoors 如何作为一个统一的框架,能够容纳文献中已知的几个可行限制,并展示了如何利用 backdoors 将参数化复杂性理论的最新算法结果应用到答案集编程领域。
Apr, 2011
本文在传统的强背门集和弱背门集的基础上,扩展了其概念,允许背门变量的不同实例属于不同的基类,形成异构基类。在此基础上,探讨了在 SAT 和 CSP 领域检测强背门集和弱背门集到异构基类的问题复杂度,提出检测到异构基类的背门集远比检测到同构基类的背门集更为可取但可能更为困难。
Sep, 2015