On complexity properties of recursively enumerable sets

DOI10.2307/2271984MaRDI QIDQ4101804zbMATH OpenOpenAlexFDO

Authors 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) Recursively (computably) enumerable sets and degrees (03D25) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites work

• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On Effective Procedures for Speeding Up Algorithms

Cited in

(23)

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

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

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