Existence versus Exploitation: The Opacity of Backbones and Backdoors Under a Weak Assumption
Backdoors and backbones of Boolean formulas are hidden structural properties. A natural goal, already in part realized, is that solver algorithms seek to obtain substantially 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 paper. In particular, 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 a structure to being able to get one's hands on it and/or being able to exploit the structure. For example, in this paper we show that, under the assumption that P $\neq$ NP, there are easily recognizable families of Boolean formulas with strong backdoors that are easy to find, yet for which it is hard (in fact, NP-complete) to determine whether the formulas are satisfiable. We also show that, also under the assumption P $\neq$ NP, there are easily recognizable sets of Boolean formulas for which it is hard (in fact, NP-complete) to determine whether they have a large backbone.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global opt…
Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models
As ML models become increasingly complex and integral to high-stakes domains such as finance and healthcare, they also become more susceptible to sophisticated adversarial attacks. We investigate the threat posed by unde…
Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning
Many real-world problems can be efficiently modeled as Mixed Integer Linear Programs (MILPs) and solved with the Branch-and-Bound method. Prior work has shown the existence of MILP backdoors, small sets of variables such…
Contrastive LearningGraph AttentionNoise-Response Analysis of Deep Neural Networks Quantifies Robustness and Fingerprints Structural Malware
The ubiquity of deep neural networks (DNNs), cloud-based training, and transfer learning is giving rise to a new cybersecurity frontier in which unsecure DNNs have `structural malware' (i.e., compromised weights and acti…
Transfer LearningRelating Complexity-theoretic Parameters with SAT Solver Performance
Over the years complexity theorists have proposed many structural parameters to explain the surprising efficiency of conflict-driven clause-learning (CDCL) SAT solvers on a wide variety of large industrial Boolean instan…