About this document

Proof Search Algorithms in Resolution and PC by Kevin Mondragon is a document available to read on EtoBox.

This document summarizes a study on the complexity of proofs in resolution and polynomial calculus proof systems. It shows that the recently proposed algorithm for searching resolution proofs cannot perform better than weakly exponential time. It also shows that translating CNF formulas with short resolution proofs to polynomials requires proofs of degree (log n) in polynomial calculus, implying its simulation of resolution is no better than quasipolynomial time. The document conjectures that this simulatio

Author

Kevin Mondragon

Language

EN