Backdoors into two occurrences

DOI10.3233/SAT-200125zbMATH Open1483.68147OpenAlexW3036111162MaRDI QIDQ5014282FDOQ5014282

Authors Jan Johannsen

Publication date 1 December 2021

Published in Journal on Satisfiability, Boolean Modeling and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/sat-200125

zbMATH Keywords

completenessfixed-parameter tractabilityparameterized complexitybackdoor setformulas with two variable occurrences

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Recommendations

• Backdoors to satisfaction
• Backdoors to acyclic SAT
• Backdoor sets for CSP
• Matched formulas and backdoor sets
• Backdoor sets for DLL subsolvers

Cites work

• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• Backdoors to satisfaction
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Parametrized complexity theory.
• STACS 2004
• Solving \#SAT using vertex covers
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Variable and term removal from Boolean formulae
• Which problems have strongly exponential complexity?

Cited in

(6)

• Backdoors to satisfaction
• Upper and lower bounds for weak backdoor set detection
• Matched formulas and backdoor sets
• Backdoor sets of quantified Boolean formulas
• Backdoor Sets of Quantified Boolean Formulas
• Matched Formulas and Backdoor Sets

This page was built for publication: Backdoors into two occurrences

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