A Lower Bound for Interpolation

DOI10.1093/JIGPAL/5.3.1-AMaRDI QIDQ4340536zbMATH OpenOpenAlexFDO

Authors Misha Gavrilovich

Publication date 26 October 1997

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/jigpal/5.3.1-a

zbMATH Keywords

interpolant of a valid implicationsize of the shortest interpolanttautologies

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the existence of polynomial time algorithms for interpolation problems in propositional logic
• scientific article; zbMATH DE number 3954886
• Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic

Cited in

(4)

• Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
• On the existence of polynomial time algorithms for interpolation problems in propositional logic
• Lower complexity bounds for interpolation algorithms
• INTERPOLATION UNDER A GRADIENT BOUND

This page was built for publication: A Lower Bound for Interpolation

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