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

DOI10.1093/logcom/7.4.457zbMath0882.68075OpenAlexW2052050541MaRDI QIDQ4351797

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)

Related Items (5)

Parameterized random complexity ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ Lower Bounds for Kernelizations and Other Preprocessing Procedures ⋮ Lower bounds for kernelizations and other preprocessing procedures ⋮ k-SAT Is No Harder Than Decision-Unique-k-SAT

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