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.
Even in the theoretical computer science world, where Borodin and Demers's work is set, the work has been very rarely used. In particular, it has been used to get characterizations regarding unambiguous computation @cite_6 , and Rothe and his collaborators have used it in various contexts to study the complexity of certificates @cite_11 @cite_10 , see also and Valiant .
@cite_10 @cite_6 @cite_11
2410312262 2100570449
In dieser Habilitationsschrift werden Struktur und Eigenschaften von Komplexitatsklassen wie P und NP untersucht, vor allem im Hinblick auf: Zertifikatkomplexitat, Einwegfunktionen, Heuristiken gegen NP-Vollstandigkeit und Zahlkomplexitat. Zum letzten Punkt werden speziell untersucht: (a) die Komplexitat von Zahleigenschaften von Schaltkreisen, (b) Separationen von Zahlklassen mit Immunitat und (c) die Komplexitat des Zahlens der Losungen von ,,tally NP-Problemen. This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for which UPA has no complete languages and other relativizations for which PB ≠ UPB ≠ NPB and UPB has complete languages. Among other results we show that P ≠ UP if and only if there exists a set S in P of Boolean formulas with at most one satisfying assignment such that S ∩ SAT is not in P. P ≠ UP ∩ coUP if and only if there exists a set S in P of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas in S. If UP has complete languages then there exists a set R in P of Boolean formulas with at most one satisfying assignment so that SAT ∩ R is complete for UP. Finally, we indicate the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic class BPP. There is a relativized world where BPPA has no complete languages. If BPP has complete languages then it has a complete language of the form B ∩ MAJORITY, where B ∈ P and MAJORITY = f | f is true for at least half of all assignments is the canonical PP-complete set.