A note on width-parameterized SAT: an exact machine-model characterization

DOI10.1016/J.IPL.2009.09.012MaRDI QIDQ990090zbMATH OpenOpenAlexFDO

Authors Periklis A. Papakonstantinou

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.09.012

zbMATH Keywords

computational complexitypathwidthSATcompletenessfixed parameter space tractabilitymachine characterization

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Some remarks on the incompressibility of width-parameterized SAT instances
• On the equivalence among problems of bounded width
• Width-parametrized SAT: time-space tradeoffs
• Theory and Applications of Satisfiability Testing
• Complexity and Algorithms for Well-Structured k-SAT Instances

Cites work

• scientific article; zbMATH DE number 1332665 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Parametrized complexity theory.
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Theory and Applications of Satisfiability Testing
• Which problems have strongly exponential complexity?

Cited in

(3)

• Some remarks on the incompressibility of width-parameterized SAT instances
• An upper bound for resolution size: characterization of tractable SAT instances
• On the equivalence among problems of bounded width

This page was built for publication: A note on width-parameterized SAT: an exact machine-model characterization

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