scientific article; zbMATH DE number 2196512

MaRDI QIDQ5465359zbMATH OpenFDO

Authors Stephen Cook

Publication date 22 August 2005

zbMATH Keywords

complexity classquantified propositional system

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Logical foundations of proof complexity
• Bounded arithmetic for NC, ALogTIME, L and NL
• Theories for TC0 and Other Small Complexity Classes
• Recent topics on bounded arithmetic and complexity theory
• scientific article; zbMATH DE number 806747

Cited in

(15)

• Uniform normal form for general time-bounded complexity classes
• Applicative theories for logarithmic complexity classes
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• On the correspondence between arithmetic theories and propositional proof systems – a survey
• A Groupoid of Isomorphic Data Transformations
• Arithmetic theories for computational complexity problems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
• Logical foundations of proof complexity
• Theories for TC0 and Other Small Complexity Classes
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)
• Short propositional refutations for dense random 3CNF formulas
• The equivalence of theories that characterize ALogTime
• Generalized quantifier and a bounded arithmetic theory for LOGCFL

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