An algebra and a logic for \(NC^ 1\)

DOI10.1016/0890-5401(90)90063-NzbMath0717.68032OpenAlexW2132858301MaRDI QIDQ2638772

Kevin J. Compton, Claude Laflamme

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90063-n

zbMATH Keywords

complexity class \(NC^ 1\)

Mathematics Subject Classification ID

Model theory (03C99) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Function-algebraic characterizations of log and polylog parallel time, Algebraic and logical characterizations of deterministic linear time classes, A logical characterization of constant-depth circuits over the reals, Tailoring recursion for complexity, A query language for NC (extended abstract), Arithmetizing uniform \(NC\), Tailoring recursion for complexity, A characterization of alternating log time by ramified recurrence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On uniform circuit complexity
• Arithmetizing uniform \(NC\)
• Weak Second‐Order Arithmetic and Finite Automata
• Classes of Predictably Computable Functions
• A taxonomy of problems with fast parallel algorithms
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Decision Problems of Finite Automata Design and Related Arithmetics
• Complexity classes and theories of finite models
• Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids