Relative complexity of operations on numeric and bit-string algebras

DOI10.1007/BF01744295zbMath0469.68046MaRDI QIDQ3923596

Edward K. Blum, Nancy A. Lynch

Publication date: 1980

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

partial recursive functionpolynomial timeflowchartreducibility relationcomputing power of various algebrasrecursive power

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of computability and recursion theory (03D80) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (4)

Straight-line program length as a parameter for complexity analysis ⋮ Relative complexity of algebras ⋮ THICKET DENSITY ⋮ Necessary and sufficient conditions for the universality of programming formalisms

Cites Work

• Unnamed Item
• A difference in expressive power between flowcharts and recursion schemes
• Relative complexity of algebras
• Straight-line program length as a parameter for complexity measures
• Real-Time Simulation of Multihead Tape Units

This page was built for publication: Relative complexity of operations on numeric and bit-string algebras