The Opacity of Backbones

Authors

  • Lane Hemaspaandra University of Rochester
  • David Narváez Rochester Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v31i1.11134

Keywords:

backbones, SAT, complexity

Abstract

A backbone of a boolean formula F is a collection S of its variables for which there is a unique partial assignment aSsuch that F[aS] is satisfiable (Monasson et al. 1999; Williams, Gomes, and Selman 2003).  This paper studies the nontransparency of backbones.  We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values, aS, of those backbones is intractable.  We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone S is intractable.  Further, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency.

Downloads

Published

2017-02-12

How to Cite

Hemaspaandra, L., & Narváez, D. (2017). The Opacity of Backbones. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.11134

Issue

Section

Main Track: Search and Constraint Satisfaction