A feasibly constructive lower bound for resolution proofs

DOI10.1016/0020-0190(90)90141-JzbMath0702.68065OpenAlexW2049059582MaRDI QIDQ915457

Toniann Pitassi, Stephen A. Cook

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90141-j

zbMATH Keywords

lower boundresolutionconstructive proofpolynomial time

Mathematics Subject Classification ID

Related Items (2)

On a generalization of extended resolution ⋮ Functional interpretations of feasibly constructive arithmetic

Cites Work

• Unnamed Item
• Resolution proofs of generalized pigeonhole principles
• The intractability of resolution
• Many hard examples for resolution
• Hard examples for resolution

This page was built for publication: A feasibly constructive lower bound for resolution proofs