A note on SAT algorithms and proof complexity

DOI10.1016/j.ipl.2012.03.009zbMath1243.68192MaRDI QIDQ436581

Jan Krajíček

Publication date: 25 July 2012

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

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

zbMATH Keywords

computational complexity; SAT algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B70: Logic in computer science

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

A remark on pseudo proof systems and hard instances of the satisfiability problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards NP-P via proof complexity and search
• On the automatizability of resolution and related propositional proof systems
• An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• Automata, Languages and Programming
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution