Arithmetizing uniform \(NC\)

DOI10.1016/0168-0072(91)90057-SzbMath0741.03019OpenAlexW2163512254MaRDI QIDQ1176198

Bill Allen

Publication date: 25 June 1992

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(91)90057-s

zbMATH Keywords

polynomial complexitybounded arithmeticBLarithmetical definabilityinduction schemataBoolean circuit definablecomplexity analysis in a bounded sequent calculuspolynomially bounded functionsrecursion definableuniform NC

Mathematics Subject Classification ID

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

Related Items

Function-algebraic characterizations of log and polylog parallel time, RSUV isomorphisms for TAC\(^ i\), TNC\(^ i\) and \(TLS\), An algebra and a logic for \(NC^ 1\), On parallel hierarchies and R ki, Computation models and function algebras, On the finite axiomatizability of, X Latin American Symposium on Mathematical Logic, Construction of models of bounded arithmetic by restricted reduced powers, Bounded arithmetic for NC, ALogTIME, L and NL, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), A new recursion-theoretic characterization of the polytime functions, A model of \(\widehat{R}^2_3\) inside a subexponential time resource, Unnamed Item, Separating NC along the \(\delta\) axis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On uniform circuit complexity
• An arithmetical characterization of NP
• Complete problems for deterministic polynomial time
• Untersuchungen über das logische Schliessen. II
• An algebra and a logic for \(NC^ 1\)
• Classes of Predictably Computable Functions
• Simulation of Parallel Random Access Machines by Circuits
• Expressibility and Nonuniform Complexity Classes
• A taxonomy of problems with fast parallel algorithms
• A logic for constant-depth circuits
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Complexity classes and theories of finite models
• Existence and feasibility in arithmetic