A lower bound for the complexity of Craig's interpolants in sentential logic

DOI10.1007/BF02023010zbMath0511.03004MaRDI QIDQ4749821

Daniele Mundici

Publication date: 1983

Published in: Archiv für Mathematische Logik und Grundlagenforschung (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/138004

zbMATH Keywords

computation theorycomplexity of boolean functionCraig's interpolantslower bound on complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Related Items (6)

Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic ⋮ The Complexity of Propositional Proofs ⋮ No feasible monotone interpolation for simple combinatorial reasoning ⋮ Natural limitations of decision procedures for arithmetic with bounded quantifiers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The network complexity and the Turing machine complexity of finite functions
• The complexity of explicit definitions
• Robinson's Consistency Theorem in Soft Model Theory
• Compactness=JEP in any logic
• Interpolation, compactness and JEP in soft model theory
• Compactness, interpolation and Friedman's third problem
• Duality Between Logics and Equivalence Relations
• The relative efficiency of propositional proof systems

This page was built for publication: A lower bound for the complexity of Craig's interpolants in sentential logic