scientific article; zbMATH DE number 3906484

MaRDI QIDQ3684112zbMATH OpenFDO

Authors Daniele Mundici

Publication date 1983

zbMATH Keywords

circuit depthcomplexity of the decision problemnondeterministic Turing timeproof lengthsentential interpolantstautologies with one interpolant

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Structure of proofs (03F07) Complexity of proofs (03F20)

Recommendations

• Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
• scientific article; zbMATH DE number 3954886
• On the existence of polynomial time algorithms for interpolation problems in propositional logic
• An improved time-space lower bound for tautologies
• An Improved Time-Space Lower Bound for Tautologies

Cited in

(4)

• Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
• scientific article; zbMATH DE number 3954886 (Why is no real title available?)
• scientific article; zbMATH DE number 1390084 (Why is no real title available?)
• On the quantifier complexity of \(\Delta_{n+1}(T)\)-induction

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 Q3684112)