scientific article; zbMATH DE number 1789924

MaRDI QIDQ4549235zbMATH OpenFDO

Authors Ran Raz

Publication date 16 June 2003

zbMATH Keywords

lower boundspigeonhole principleproof theoryresolutionresolution proofweak pigeonhole principle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Resolution lower bounds for the weak pigeonhole principle
• Regular resolution lower bounds for the weak pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• Regular resolution lower bounds for the weak pigeonhole principle

Cited in

(6)

• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• The Complexity of Propositional Proofs
• Resolution lower bounds for the weak pigeonhole principle
• Propositional proof complexity
• Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
• Exponential lower bounds for the pigeonhole principle

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 Q4549235)