Parameterized Complexity of DPLL Search Procedures
From MaRDI portal
Publication:5892172
DOI10.1145/2499937.2499941zbMath1354.68105OpenAlexW2045690379WikidataQ59901045 ScholiaQ59901045MaRDI QIDQ5892172
Nicola Galesi, Massimo Lauria, Olaf Beyersdorff
Publication date: 17 September 2015
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: http://eprints.whiterose.ac.uk/79311/8/para-dpll.pdf
Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity of proofs (03F20)
Related Items
Narrow Proofs May Be Maximally Long, Proof complexity of modal resolution, Tight size-degree bounds for sums-of-squares proofs, A game characterisation of tree-like Q-resolution size, The complexity of proving that a graph is Ramsey, Cliques enumeration and tree-like resolution proofs, A Game Characterisation of Tree-like Q-resolution Size, Parameterized Complexity of DPLL Search Procedures, Resolution and the binary encoding of combinatorial principles, Large clique is hard on average for resolution
