scientific article; zbMATH DE number 3799636

MaRDI QIDQ4744264zbMATH OpenFDO

Authors Daniele Mundici

Publication date 1982

zbMATH Keywords

circuit depthcircuit sizeCraig interpolationNPpropositional calculustransitive closureuniform and non- uniform complexity

Mathematics Subject Classification ID

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

Cited in

(6)

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

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)