On the complexity of the ℰ2 Grzegorczyk class

DOI10.1515/DMA.2010.003MaRDI QIDQ3586259zbMATH OpenFDO

Authors S. S. Marchenkov

Publication date 6 September 2010

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

zbMATH Keywords

Minsky machinesarithmetic functionsprimitive recursive functionsGrzegorczyk hierarchy

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• The complexity to compute the Euler characteristic of complex varieties
• On the complexity of computing Gröbner bases in characteristic 2
• A generalized Grzegorczyk hierarchy and low complexity classes
• On the Graver complexity of codimension \(2\) matrices
• On the Gröbner complexity of matrices
• Complexity of conjugacy classes of \(A(\mathbb Q)\)
• scientific article; zbMATH DE number 3996316
• On the complexity of the computation of certain classes of polynomials of several variables
• scientific article; zbMATH DE number 1823886
• Complexity classes and completeness in algebraic geometry

Cites work

• Classes of languages and linear-bounded automata

Cited in

(4)

• A generalized Grzegorczyk hierarchy and low complexity classes
• Near-polynomial recursive sequences with algorithmically unsolvable problems
• An example of a simple quasi-universal function in the class ε 2 of the Grzegorczyk hierarchy
• An inherently iterative algorithm for the Grzegorczyk hierarchy

This page was built for publication: On the complexity of the ℰ2 Grzegorczyk class

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