The Opacity of Backbones

Lane A. Hemaspaandra, David E. NarváezAAAI 2017 · DOI

TL;DR

This paper investigates the computational difficulty of working with "backbones" of Boolean formulas, which are unique partial assignments that determine satisfiability. The authors show that even when a backbone is easy to identify, finding its specific assignment can be computationally intractable, and conversely, finding a large backbone can be difficult, assuming widely held beliefs about the hardness of integer factorization.

What Problem Does This Paper Address?

The field of SAT (Satisfiability) solving deals with determining whether a given Boolean formula can be satisfied. A key concept in understanding the structure of solutions to SAT problems is the "backbone" of a formula. A backbone is a set of variables for which there's a unique partial assignment that makes the formula satisfiable. Intuitively, these "frozen variables" can simplify the search for satisfying assignments. The authors explore the practical implications of this concept: if we can easily recognize that a formula has a backbone, can we also easily find that backbone or its specific assignment? They aim to show that, under standard complexity assumptions, the answer is often no, highlighting a potential "opacity" in how easily we can leverage backbones.

Methods

The paper's core contribution lies in constructing specific sets of Boolean formulas that demonstrate the opacity of backbones. They leverage a strengthened version of the Cook-Karp-Levin reduction, specifically the "Galil-Cook" reduction, which allows for the creation of formulas that transparently reveal the machine and input used in the reduction. This is crucial for controlling the structure and properties of the resulting formulas and their backbones. The proofs involve constructing sets of formulas where:

  1. A polynomial-time computable function can identify a nontrivial backbone.
  2. No polynomial-time computable function can find the value (the specific assignment) of that identified backbone.

They also construct sets of formulas where:

  1. A formula is guaranteed to have a large backbone (a significant percentage of its variables).
  2. No polynomial-time computable function can efficiently find any backbone of that significant size.

A key aspect of their work is also addressing the frequency of these hardness results, showing that these "opaque" scenarios occur with a density comparable to the hardest problems in NP ∩ coNP, assuming integer factorization is hard on average.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions of formula sets rather than empirical evaluation on existing datasets.

Key Insights and Ideas

  • Backbones are not always practically useful: While the existence of a backbone is a structural property, finding its specific assignment or even a large backbone can be computationally hard, even if the formula itself is satisfiable and its backbone is easily identifiable.
  • Complexity assumptions matter: The results hinge on the assumption that P ≠ NP ∩ coNP, which is widely believed to be true and is implied by the hardness of integer factorization. This connects theoretical computer science concepts to practical cryptographic assumptions.
  • Frequency of hardness is important: The paper goes beyond worst-case hardness to show that these "opacity" issues are not rare occurrences but can be made to happen with a frequency comparable to the most difficult problems in NP ∩ coNP. This addresses potential skepticism about the practical relevance of theoretical hardness results.
  • Galil-Cook reduction is a powerful tool: The paper demonstrates a sophisticated use of the Galil-Cook reduction to construct formulas with specific, controllable properties related to their backbones.

Key Results

  • Theorem 1 & 2: If P ≠ NP ∩ coNP, there exist satisfiable formula sets where a nontrivial (or size-k) backbone can be found in polynomial time, but its specific assignment cannot.
  • Theorem 3 & 4: If P ≠ NP ∩ coNP, there exist satisfiable formula sets where formulas have large backbones (e.g., 49% of variables), but finding any backbone of a significant size (e.g., 2% of variables) is intractable.
  • Theorem 5 & 6: Under assumptions about the frequency of hardness in NP ∩ coNP (e.g., integer factorization being frequently hard), the opacity results for finding backbone values and large backbones hold with a density "almost" as high as the hardest problems in NP ∩ coNP.

Limitations and Future Work

  • Assumption dependence: The core results rely on the assumption P ≠ NP ∩ coNP. The authors briefly mention that weaker results might be obtainable under the assumption P = NP, but these are considered less satisfying.
  • "Almost" frequency: While the paper addresses frequency, the "almost" in "almost as frequently" introduces a constant factor in an exponent, which can still lead to significant numerical differences in error rates. The exact value of this constant depends on the complexity of the underlying NP ∩ coNP problems.
  • Future work: The paper suggests exploring whether similar opacity results can be achieved under weaker assumptions than P ≠ NP ∩ coNP. The authors also note that their constructions are designed for communication and not necessarily for extreme rigor, implying that further formalization might be needed for certain theoretical contexts.

Summary updated

BibTeX
@inproceedings{hemaspaandra2017opacity,
  author = {Lane A. Hemaspaandra and David E. Narváez},
  title = {{The Opacity of Backbones}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11134},
}
Figure