scientific article; zbMATH DE number 3799636

MaRDI QIDQ4744264zbMATH OpenFDO

Authors Daniele Mundici

Publication date 1982

zbMATH Keywords

transitive closureCraig interpolationcircuit depthcircuit sizeNPpropositional calculusuniform and non- uniform complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cited in

(6)

• Interpolation systems for ground proofs in automated deduction: a survey
• A lower bound for the complexity of Craig's interpolants in sentential logic
• Progression of decomposed local-effect action theories
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Finite-Variable Logics Do Not Have Weak Beth Definability Property
• Natural limitations of decision procedures for arithmetic with bounded quantifiers

This page was built for publication:

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