scientific article; zbMATH DE number 1114018

MaRDI QIDQ4375787zbMATH OpenFDO

Authors Stephen Cook

Publication date 30 June 1998

zbMATH Keywords

complexity classespolynomial-timeconservativityfirst-order theoriesopen induction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• From Collapse Theorems to Proof-Theoretic Arguments
• scientific article; zbMATH DE number 3966034
• On the structure of the degrees of relative provability
• scientific article; zbMATH DE number 4006256
• Theories of proof-theoretic strength \(\psi(\Gamma_{\Omega+1})\)
• AXIOMATIZATION OF PROVABLE n-PROVABILITY
• On Relating Theories: Proof-Theoretical Reduction
• Axiomatizing provable \(n\)-provability
• scientific article; zbMATH DE number 2020228
• The polytopologies of transfinite provability logic

Cited in

(6)

• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• The equivalence of theories that characterize ALogTime
• The enumerability of P collapses P to NC
• A second-order system for polytime reasoning based on Grädel's theorem.
• Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II
• A bounded arithmetic AID for Frege systems

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