SAT-Problems and Reductions with Respect to the Number of Variables
From MaRDI portal
Publication:4351797
DOI10.1093/LOGCOM/7.4.457zbMATH Open0882.68075OpenAlexW2052050541MaRDI QIDQ4351797FDOQ4351797
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
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
- Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
- SAT problems with chains of dependent variables
- Fixed-parameter tractable reductions to SAT
- Local reduction
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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)
