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

Sep, 2015

Backdoors into Heterogeneous Classes of SAT and CSP

Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, Stanislav Živný

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

Abstract

In this paper we extend the classical notion of strong and weak backdoor sets by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. →