SAT-Problems and Reductions with Respect to the Number of Variables

DOI10.1093/LOGCOM/7.4.457MaRDI QIDQ4351797zbMATH OpenOpenAlexFDO

Authors Etienne Grandjean, Hans Kleine Büning

Publication date 28 August 1997

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/7.4.457

zbMATH Keywords

polynomial time bounded reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A polynomial-time algorithm for reducing the number of variables in MAX SAT problem
• Fixed-parameter tractable reductions to SAT
• scientific article; zbMATH DE number 3871314
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Efficient SAT solving under assumptions
• On SAT Modulo Theories and Optimization Problems
• On Some SAT-Variants over Linear Formulas
• Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
• A note on SAT algorithms and proof complexity

Cited in

(13)

• Lower bounds for kernelizations and other preprocessing procedures
• Lower bounds for kernelizations and other preprocessing procedures
• SAT problems with chains of dependent variables
• Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
• Fixed-parameter tractable reductions to SAT
• Local reduction
• scientific article; zbMATH DE number 2201270 (Why is no real title available?)
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• k-SAT Is No Harder Than Decision-Unique-k-SAT
• Parameterized random complexity
• Reducing symmetries to generate easier SAT instances
• scientific article; zbMATH DE number 5914170 (Why is no real title available?)
• Local reductions

This page was built for publication: SAT-Problems and Reductions with Respect to the Number of Variables

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