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

DOI10.1016/J.IPL.2009.09.012zbMATH Open1206.68150OpenAlexW1981679584MaRDI QIDQ990090FDOQ990090

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

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

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)

Cites Work

• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Which problems have strongly exponential complexity?
• Parametrized complexity theory.
• Theory and Applications of Satisfiability Testing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity and Algorithms for Well-Structured k-SAT Instances

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)