scientific article; zbMATH DE number 2196512
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)
This article begins thus: ``An important part of bounded arithmetic is associating logical theories with various complexity classes, and then translating proofs in those theories to families of proofs in appropriate propositional (or quantified propositional) proof systems. Our purpose here is to give a unified treatment of this three-way association to the sequence of complexity classes \[ \text{AC}^0\subset \text{AC}^0(2)\subset \text{TC}^0\subseteq \text{NC}^1\subseteq \text{L}\subseteq \text{NL}\subseteq \text{NC}\subseteq \text{P}, \] where P is the class of problems solvable in polynomial time. As the author says, ``in the literature there is a hodge-podge of theories associated with these complexity classes -- equational, 1-sorted, 2-sorted, etc. Hence, a good unified treatment as in this article is certainly a great service. The author uses 2-sorted languages (one sort for numbers, and the other for finite sequences of 0 and 1). He starts from basic definitions, explains each complexity class, and sets up the matching theory. Of course, the correctness of the match is proved or referred to the literature. Translations into quantified propositional systems are carefully given, but not many results or theorems are mentioned. There are abundant comments on past achievements and future work, including the comparison of the author's 2-sorted approach with Krajíček's 1-sorted one. For the entire collection see [Zbl 1062.68004].
- 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)