The opacity of backbones

DOI10.1016/j.ic.2021.104772OpenAlexW3176999014MaRDI QIDQ2051797

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

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• The complexity of computing the permanent
• Generalized juntas and NP-hard sets
• The complexity of parallel search
• Complexity classes without machines: on complete languages for UP
• Relative complexity of checking and evaluating
• Easy sets and hard certificate schemes
• Inverting onto functions.
• The Complexity of Decision Versus Search
• Complete sets and closeness to complexity classes
• Reducibility among Combinatorial Problems
• Search versus Decision for Election Manipulation Problems
• Determining computational complexity from characteristic ‘phase transitions’
• The complexity of theorem-proving procedures

This page was built for publication: The opacity of backbones