On complexity properties of recursively enumerable sets

DOI10.2307/2271984zbMath0335.02024OpenAlexW1975592766MaRDI QIDQ4101804

Ivan Marques, Manuel Blum

Publication date: 1974

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2271984

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (22)

On speedable and levelable vector spaces ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Lower bounds on degrees of game-theoretic structures ⋮ The structure of generalized complexity cores ⋮ Unnamed Item ⋮ \(sQ_1\)-degrees of computably enumerable sets ⋮ Infimums of step-counting functions of enumeration of sets ⋮ Some reducibilities and splittings of recursively enumerable sets ⋮ On p-creative sets and p-completely creative sets ⋮ On the bounded quasi‐degrees of c.e. sets ⋮ Complexity properties of recursively enumerable sets and \(bsQ\)-completeness ⋮ On computational complexity and honest polynomial degrees ⋮ Kolmogorov entropy in the context of computability theory ⋮ The complexity of total order structures ⋮ Some lowness properties and computational complexity sequences ⋮ Upper semilattice of recursively enumerable sQ-degrees ⋮ Recursively enumerable sets and degrees ⋮ Complexity properties of recursively enumerable sets and \(sQ\)-completeness ⋮ Classes of recursively enumerable sets and Q-reducibility ⋮ Splitting theorems in recursion theory ⋮ Upper semilattice of recursively enumerable Q-degrees ⋮ Degree structures of conjunctive reducibility

Cites Work

• Unnamed Item
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On Effective Procedures for Speeding Up Algorithms

This page was built for publication: On complexity properties of recursively enumerable sets