On complexity properties of recursively enumerable sets
From MaRDI portal
Publication:4101804
DOI10.2307/2271984zbMath0335.02024OpenAlexW1975592766MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)
Related Items
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
