Short Resolution refutations of Ref(φ) yield satisfying assignments for φ in polynomial time via a PV1-formalizable construction, and the Proof Analysis Problem is NP-complete for Extended Frege.
Theory of Computing Systems , year = 2010, month =
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.CC 2verdicts
UNVERDICTED 2representative citing papers
The paper establishes the first lower bounds on roABP-IPS refutation size for CNF formulas via a rank-based feasible interpolation argument.
citing papers explorer
-
The Proof Analysis Problem
Short Resolution refutations of Ref(φ) yield satisfying assignments for φ in polynomial time via a PV1-formalizable construction, and the Proof Analysis Problem is NP-complete for Extended Frege.
-
Hard CNF Instances for Ideal Proof Systems
The paper establishes the first lower bounds on roABP-IPS refutation size for CNF formulas via a rank-based feasible interpolation argument.