The Opacity of Backbones
This addresses a foundational issue in computational complexity theory, revealing inherent opacity in structures like backbones, which is incremental as it builds on prior work on backbones and hardness assumptions.
The paper tackles the problem of whether knowing a backbone exists in boolean formulas is sufficient to efficiently compute it, showing that under the assumption that integer factoring is hard, there exist formulas where finding backbone values or producing the backbone itself is intractable, with results extending to settings where P ≠ NP ∩ coNP or problems in NP ∩ coNP are frequently hard.
This paper approaches, using structural complexity theory, the question of whether there is a chasm between knowing an object exists and getting one's hands on the object or its properties. In particular, we study the nontransparency of so-called backbones. A backbone of a boolean formula $F$ is a collection $S$ of its variables for which there is a unique partial assignment $a_S$ such that $F[a_S]$ is satisfiable [MZK+99,WGS03]. 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, $a_S$, 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. Furthermore, 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. These results hold more generally, namely, in the settings where, respectively, one's assumption is that P $\neq$ NP $\cap$ coNP or that some problem in NP $\cap$ coNP is frequently hard.