An optimal lower bound for resolution with 2-conjunctions

DOI10.1007/3-540-45687-2_32MaRDI QIDQ4708587zbMATH OpenFDO

Authors Jan Johannsen, N. S. Narayanaswamy

Publication date 18 June 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/2420/24200387.htm

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the complexity of resolution with bounded conjunctions
• scientific article; zbMATH DE number 2086624
• Parameterized resolution with bounded conjunction
• A feasibly constructive lower bound for resolution proofs
• Resolution-based lower bounds in MaxSAT
• An upper bound for minimal resolution refutations
• A conditional superpolynomial lower bound for extended resolution
• Minimum 2CNF Resolution Refutations in Polynomial Time
• Tight lower bounds on the resolution complexity of perfect matching principles
• On exponential lower bounds for partially ordered resolution

Cited in

(6)

• Resolution with counting: dag-like lower bounds and different moduli
• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• A near-optimal separation of regular and general resolution
• Hard examples for resolution
• An upper bound for minimal resolution refutations
• scientific article; zbMATH DE number 7650367 (Why is no real title available?)

This page was built for publication: An optimal lower bound for resolution with 2-conjunctions

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