A note on SAT algorithms and proof complexity

DOI10.1016/J.IPL.2012.03.009zbMath1243.68192OpenAlexW2009304285MaRDI 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 complexitySAT algorithms

Mathematics Subject Classification ID

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

Related Items (2)

INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on SAT algorithms and proof complexity