The opacity of backbones

DOI10.1016/J.IC.2021.104772MaRDI QIDQ2051797zbMATH OpenOpenAlexFDO

Authors David E. Narváez, Lane A. Hemaspaandra

Publication date 25 November 2021

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.03634

zbMATH Keywords

backbonesstructural complexity theory\( \operatorname{NP} \cap \operatorname{coNP} \)frequency of hardness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption
• Local backbones
• On computing backbones of propositional theories
• A note on backbones in optimization and approximation
• scientific article; zbMATH DE number 169728

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1482586 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• Complete sets and closeness to complexity classes
• Complexity classes without machines: on complete languages for UP
• Determining computational complexity from characteristic ``phase transitions
• Easy sets and hard certificate schemes
• Generalized juntas and NP-hard sets
• Inverting onto functions.
• Junta distributions and the average-case complexity of manipulating elections
• Reducibility among combinatorial problems
• Relative complexity of checking and evaluating
• Search versus Decision for Election Manipulation Problems
• The Complexity of Decision Versus Search
• The complexity of computing the permanent
• The complexity of parallel search
• The complexity of theorem-proving procedures
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search

Cited in

(1)

• Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption

This page was built for publication: The opacity of backbones

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051797)