scientific article; zbMATH DE number 1929954

MaRDI QIDQ4708587zbMATH OpenFDO

Authors Jan Johannsen, N. S. Narayanaswamy

Publication date 18 June 2003

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
• scientific article; zbMATH DE number 1342212
• 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
• scientific article; zbMATH DE number 1342212 (Why is no real title available?)
• scientific article; zbMATH DE number 7650367 (Why is no real title available?)

This page was built for publication:

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