Existence versus exploitation: the opacity of backdoors and backbones
Existence versus exploitation: the opacity of backdoors and backbones
复制标题
存在与剥削：后门和主干的不透明性
DOI：
10.1007/s13748-021-00234-6
复制
发表时间：
2021
影响因子：
4.2
通讯作者：
Narváez, David E.
中科院分区：
文献类型：
--
作者：
Hemaspaandra, Lane A.;Narváez, David E.
布尔公式通常具有所谓的隐藏结构。我们研究公式中是否存在此类结构（具有一定大小）的复杂性、获取结构信息的复杂性，以及即使掌握了信息是否也能被有效利用。特别是，布尔公式的后门和主干是重要的隐藏结构属性。一个自然的目标（已经部分实现）是求解器算法通过利用这些结构来寻求更好的性能。然而，本文并不是为了提高 SAT 求解器的性能，而是一个警示故事。本文的主题是布尔公式中此类结构的存在与有效利用它们之间存在潜在的鸿沟。这并不意味着这些结构对求解器没有用处。这确实意味着人们必须非常小心，不要假设从信息的存在到能够获得信息和/或能够利用它在计算上是很容易的。我们构建基于后门和主干的案例，如果这些假设失败的话。例如，如果，那么（a）存在容易识别的布尔公式族，它们很容易找到，但很难确定这些公式是否可满足；（b）存在容易识别的布尔公式集，但很难确定它们是否具有大主干。
Boolean formulas often have what are known as hidden structures. We study the complexity of whether such structures (of certain sizes) exist in a formula, the complexity of getting one’s hands on the structure’s information, and whether even when in hand the information can be efficiently exploited. In particular, backdoors and backbones of Boolean formulas are important hidden structural properties. A natural goal, already in part realized, is that solver algorithms seek better performance by exploiting these structures. However, the present paper is not intended to improve the performance of SAT solvers, but rather is a cautionary tale. The theme of this paper is that there is a potential chasm between the existence of such structures in the Boolean formula and being able to effectively exploit them. This does not mean that these structures are not useful to solvers. It does mean that one must be very careful not to assume that it is computationally easy to go from the existence of information to being able to get one’s hands on it and/or being able to exploit it. We construct backdoor- and backbone-based cases where, if, such assumptions fail. For example, if, then (a) there are easily recognizable families of Boolean formulas with strong backdoors that are easy to find, yet for which it is hard to determine whether the formulas are satisfiable, and (b) there are easily recognizable sets of Boolean formulas for which it is hard to determine whether they have a large backbone.
登录
查看更多内容
国际自动机、语言和编程研讨会 自动机、语言和编程
DOI：
--
发表时间：
1986
期刊：
影响因子：
--
作者：
L. Kott
通讯作者：
L. Kott
检查和评估的相对复杂性
影响因子：
0.5
作者：
L. Valiant
通讯作者：
L. Valiant
DOI：
10.1007/s10817-005-9007-9
发表时间：
2005-10
期刊：
Journal of Automated Reasoning
影响因子：
--
作者：
Stefan Szeider
通讯作者：
Stefan Szeider
DOI：
10.1145/3369937
发表时间：
2012
期刊：
ACM Transactions on Computation Theory (TOCT)
影响因子：
--
作者：
E. Hemaspaandra;L. Hemaspaandra;Curtis Menton
通讯作者：
Curtis Menton
SIGACT新闻复杂性理论专栏76：典型案例启发式算法的非典型调查
DOI：
--
发表时间：
2012
期刊：
SIGA
影响因子：
--
作者：
L. Hemaspaandra;Ryan Williams
通讯作者：
Ryan Williams