The complexity of total order structures

DOI10.1016/0022-0000(78)90008-9zbMath0396.03034OpenAlexW1988183602MaRDI QIDQ1253249

John Case, Dan Moore

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90008-9

zbMATH Keywords

Computational ComplexityRecursively Enumerable SetsRecursive FunctionSpeedupTotal Order

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Almost Everywhere Complex Recursive Functions
• On complexity properties of recursively enumerable sets
• Sortability and Extensibility of the Graphs of Recursively Enumerable Partial and Total Orders
• On the Computational Complexity of Algorithms
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Toward a Theory of Enumerations
• Speed-Ups by changing the order in which sets are enumerated
• Computational speed-up by effective operators

This page was built for publication: The complexity of total order structures