Relative complexity of operations on numeric and bit-string algebras

DOI10.1007/BF01744295zbMATH Open0469.68046MaRDI QIDQ3923596FDOQ3923596

Authors: Edward K. Blum, Nancy Lynch 

Publication date: 1980

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

zbMATH Keywords

polynomial timepartial recursive functionflowchartreducibility relationcomputing power of various algebrasrecursive power

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A difference in expressive power between flowcharts and recursion schemes
• Real-Time Simulation of Multihead Tape Units
• Relative complexity of algebras
• Straight-line program length as a parameter for complexity measures

Cited In (4)

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

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

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