No feasible monotone interpolation for simple combinatorial reasoning

DOI10.1016/S0304-3975(99)00142-5zbMath0947.68129OpenAlexW2075231625WikidataQ126812394 ScholiaQ126812394MaRDI QIDQ1575265

Noriko H. Arai

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00142-5

zbMATH Keywords

proof theoryautomated theorem provingproof complexityCraig's interpolation theorem

Mathematics Subject Classification ID

Related Items

Relative efficiency of propositional proof systems: Resolution vs. cut-free LK

Cites Work

• Tractability of cut-free Gentzen type propositional calculus with permutation inference
• Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II
• Lower bounds for resolution and cutting plane proofs and monotone computations
• A lower bound for the complexity of Craig's interpolants in sentential logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: No feasible monotone interpolation for simple combinatorial reasoning