scientific article; zbMATH DE number 3799636

zbMath0507.03025MaRDI QIDQ4744264

Daniele Mundici

Publication date: 1982

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

transitive closureCraig interpolationpropositional calculuscircuit depthcircuit sizeNPuniform and non- uniform complexity

Mathematics Subject Classification ID

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

Related Items (6)

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

This page was built for publication: