A backbone of a boolean formula @math is a collection @math of its variables for which there is a unique partial assignment @math such that @math is satisfiable [MZK+99,WGS03]. 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, @math , 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 @math 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.
There has been just one paper that previously has sought to bring the focus of this line to a topic of interest in AI @. Although it appeared in a theoretical computer science venue, the work of Hemaspaandra, Hemaspaandra, and Menton shows that some problems from computational social choice theory, a subarea of multiagent systems, have the property that if @math then their search versions are not polynomial-time Turing reducible to their decision problems---a rare behavior among the most familiar seemingly hard sets in computer science, since so-called self-reducibility @cite_8 is known to preclude that possibility for most standard NP-complete problems. The key issue that 2013 paper left open is whether the type of techniques it used, descended from Borodin and Demers , might be relevant anywhere else in AI, or whether its results were a one-shot oddity. The present paper in effect is arguing that the former is the case. Backbones are a topic important in AI and relevant to @math solvers, and this paper shows that the inspiration of the line of work initiated by Borodin and Demers can be used to establish the opacity of backbones.
@cite_8
1924765640
Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated, rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If integer factoring is hard, then for election manipulation, election bribery, and some types of election control, there are election systems for which recognizing which instances can be successfully manipulated is in polynomial time but producing the successful manipulations cannot be done in polynomial time.