On complexity properties of recursively enumerable sets
From MaRDI portal
Publication:4101804
DOI10.2307/2271984zbMath0335.02024MaRDI QIDQ4101804
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
68Q25: Analysis of algorithms and problem complexity
03D20: Recursive functions and relations, subrecursive hierarchies
03D25: Recursively (computably) enumerable sets and degrees
Related Items
On the bounded quasi‐degrees of c.e. sets, Complexity properties of recursively enumerable sets and \(bsQ\)-completeness, Kolmogorov entropy in the context of computability theory, Upper semilattice of recursively enumerable Q-degrees, Lower bounds on degrees of game-theoretic structures, The structure of generalized complexity cores, Infimums of step-counting functions of enumeration of sets, On p-creative sets and p-completely creative sets, The complexity of total order structures, Some lowness properties and computational complexity sequences, Complexity properties of recursively enumerable sets and \(sQ\)-completeness, Splitting theorems in recursion theory, On speedable and levelable vector spaces, Upper semilattice of recursively enumerable sQ-degrees, Classes of recursively enumerable sets and Q-reducibility, Some reducibilities and splittings of recursively enumerable sets, Degree structures of conjunctive reducibility, On computational complexity and honest polynomial degrees, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, Unnamed Item, Recursively enumerable sets and degrees
Cites Work