Apr, 2014

可追溯的约束语言的后门问题

PDF
TL;DR本文对基于约束满足问题的多项式算法强后门检测问题进行了系统研究，特别是当目标属性是由多项式函数族定义的特定约束语言时，我们表明在多项式函数族是幂等的假设下，当参数为 r（约束元数）或 k（后门大小）时，问题不可能是 FPT，除非 P = NP 或 FPT = W [2]。但是当参数为 k + r 时，我们能够识别出大量语言，以便找到小后门的问题是 FPT。
cspsbackdoor detectionparameterized complexityconstraint languagepolymorphisms
发现论文，激发创造
  • 无环可满足性问题的后门

    研究使用一个特殊的集合来使得一类复杂计算问题变得简单化的方法，利用该方法可以实现 CNF 公式求解的多项式时间算法，同时该研究提出了一些关于求解 backdoor sets 大小和检测方法的结论。

    Oct, 2011

  • 无限域约束满足问题中的计算捷径

    研究 CSP 实例的后门问题，提出了一种泛化后门概念，即面向具有高元数约束的 CSP，并介绍了 sidedoors 作为对二元约束不利的替代方案，降低了算法复杂度和提高了计算效率。

    Nov, 2022

  • 有界树宽 SAT 的强背门

    本文结合分解性和后门集两种方法，研究了在与给定 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

  • 结合树宽和后门求解 CSP 问题

    本研究论文表明，当以任何可转化为有限约束语言的可解 CSP 问题作为背景门限时，CSP 是固定参数可解的，这将结合了两个解决 CSP 可解性问题的突出方法：(i) 通过变量和约束之间交互的结构限制和 (ii) 通过内部约束所使用的关系的语言限制。除了定义背景门限的概念并展示如何利用小的背景门限来高效求解 CSP 之外，本文主要技术贡献是提出了一种寻找小背景门限的固定参数算法。

    Oct, 2016

  • 对 SAT 和 CSP 两个异构类别的后门

    本文在传统的强背门集和弱背门集的基础上，扩展了其概念，允许背门变量的不同实例属于不同的基类，形成异构基类。在此基础上，探讨了在 SAT 和 CSP 领域检测强背门集和弱背门集到异构基类的问题复杂度，提出检测到异构基类的背门集远比检测到同构基类的背门集更为可取但可能更为困难。

    Sep, 2015

  • 满意的后门

    该文章讨论了后门集合及其相关问题的参数化复杂度结果，主要研究内容包括：发现大小不超过 k 的后门集合问题、易处理问题以及适用于 NP 问题的后门集合问题等。

    Oct, 2011

  • 整数规划后门发现：一种蒙特卡罗树搜索框架

    提出了一种基于 Monte Carlo Tree Search- BaMCTS 算法，在 Mixed Integer Linear Programming（MIP）中通过构建 backdoor（后门） 数据集来提高 MIP 问题的求解效率。该算法与传统 MIP 概念相结合，且与 CPLEX 求解器紧密集成，成功地优化了 MIPLIB2017 示例的求解效率。

    Oct, 2021

  • 关于在 SAT 中使用后门的加密攻击

    本文提出一种新的 SAT 后门集类别，用于密码攻击中的猜测和确定攻击，通过使用 SAT 求解器识别最佳的后门变量集以及统计预估硬度，实验结果显示该方法较现有技术在反推攻击的硬度方面具有优势。

    Mar, 2018

  • 发现解约束满足和计数问题的可解群岛

    本文介绍了一个算法，用于找到具有给定列表中的类中的离散类的强后门，这些类由 CSP 实例中的连通分量确定，并表明满足特定条件时，可以通过这种方式超越 CSP 的易处理性限制。

    Jul, 2015

  • 可行的答案集编程后门

    本文介绍了如何使用 backdoors 的概念来识别能够使 ASP 问题可行的新限制，展示了 backdoors 如何作为一个统一的框架，能够容纳文献中已知的几个可行限制，并展示了如何利用 backdoors 将参数化复杂性理论的最新算法结果应用到答案集编程领域。

    Apr, 2011