Characterizing NC with tier 0 pointers

DOI10.1002/MALQ.200310070MaRDI QIDQ4458695zbMATH OpenOpenAlexFDO

Authors Isabel Oitavem

Publication date 15 March 2004

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200310070

zbMATH Keywords

algebra-basedimplicit characterizationNCpointerstree recursion

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Towards an Implicit Characterization of NC k
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• Recursion Schemata for NC k
• An algebra and a logic for \(NC^ 1\)
• scientific article; zbMATH DE number 176199

Cited in

(7)

• The polynomial hierarchy of functions and its levels
• Implicit recursion-theoretic characterizations of counting classes
• Algorithmically broad languages for polynomial time and space
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• Recursion Schemata for NC k
• Towards an Implicit Characterization of NC k
• A recursion-theoretic approach to NP

This page was built for publication: Characterizing NC with tier 0 pointers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4458695)