The opacity of backbones

DOI10.1016/J.IC.2021.104772OpenAlexW3176999014MaRDI QIDQ2051797FDOQ2051797

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)