On determining the minimum length, tree-like resolution refutation of 2SAT, and extended 2SAT formulas

DOI10.1007/3-540-36184-7_7MaRDI QIDQ4417352zbMATH OpenFDO

Authors K. Subramani

Publication date 29 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2550/25500057.htm

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Optimal length tree-like resolution refutations for 2SAT formulas
• Minimum Witnesses for Unsatisfiable 2CNFs
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• On resolution with short clauses
• Complexity of finding short resolution proofs

Cited in

(6)

• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• Hard examples for resolution
• Complexity of finding short resolution proofs
• Optimal length tree-like resolution refutations for 2SAT formulas
• Minimum Witnesses for Unsatisfiable 2CNFs
• Optimal length resolution refutations of difference constraint systems

This page was built for publication: On determining the minimum length, tree-like resolution refutation of 2SAT, and extended 2SAT formulas

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