Reducibility and Completeness for Sets of Integers
From MaRDI portal
Publication:3843613
DOI10.1002/malq.19590050703zbMath0108.00602OpenAlexW2024373817MaRDI QIDQ3843613
Hartley jun. Rogers, Richard M. Friedberg
Publication date: 1959
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19590050703
Related Items (63)
Enumeration 1-genericity in the local enumeration degrees ⋮ Intervals and sublattices of the r.e. weak truth table degrees. I: Density ⋮ There exists a maximal 3-c.e. enumeration degree ⋮ Strong enumeration reducibilities ⋮ Jumps of quasi-minimal enumeration degrees ⋮ Computability in Symbolic Dynamics ⋮ Splittings of effectively speedable sets and effectively levelable sets ⋮ RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS ⋮ Unnamed Item ⋮ Deficiency Sets and Bounded Information Reducibilities ⋮ A STRUCTURAL DICHOTOMY IN THE ENUMERATION DEGREES ⋮ Infima in the recursively enumerable weak truth table degrees ⋮ Agreement reducibility ⋮ Unnamed Item ⋮ The enumeration degrees: Local and global structural interactions ⋮ Badness and jump inversion in the enumeration degrees ⋮ The relationship between local and global structure in the enumeration degrees ⋮ PA RELATIVE TO AN ENUMERATION ORACLE ⋮ Splitting and nonsplitting in the \(\Sigma_2^0\) enumeration degrees ⋮ Which number theoretic problems can be solved in recursive progressions on Π11-paths through O? ⋮ Incomparability in local structures of \(s\)-degrees and \(Q\)-degrees ⋮ Enumeration Reducibility and Computable Structure Theory ⋮ There Are No Maximal d.c.e. wtt-degrees ⋮ Density of the cototal enumeration degrees ⋮ Avoiding uniformity in the \(\Delta_2^0\) enumeration degrees ⋮ Cupping and definability in the local structure of the enumeration degrees ⋮ Interpreting true arithmetic in the local structure of the enumeration degrees ⋮ Computing sets from all infinite subsets ⋮ Bounding and nonbounding minimal pairs in the enumeration degrees ⋮ Recursive Linear Orders with Incomplete Successivities ⋮ On the structures inside truth-table degrees ⋮ Contiguity and distributivity in the enumerable Turing degrees ⋮ Stochastic \(\lambda\)-calculi: an extended abstract ⋮ The \(n\)-rea enumeration degrees are dense ⋮ Immunity properties and strong positive reducibilities ⋮ Defining totality in the enumeration degrees ⋮ Using computability to measure complexity of algebraic structures and classes of structures ⋮ C-quasi-minimal enumeration degrees below \(\mathbf c'\) ⋮ Complexity properties of recursively enumerable sets and \(bsQ\)-completeness ⋮ Fragments of the theory of the enumeration degrees ⋮ Is it harder to factor a polynomial or to find a root? ⋮ Unnamed Item ⋮ Characterizing the continuous degrees ⋮ Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets ⋮ Constructive dimension and Turing degrees ⋮ INITIAL SEGMENTS OF THE ENUMERATION DEGREES ⋮ A Theorem on Intermediate Reducibilities ⋮ Recursively enumerable sets and degrees ⋮ T-Degrees, Jump Classes, and Strong Reducibilities ⋮ Vladimir Andreevich Uspensky (27/11/1930–27/6/2018) ⋮ On restricted forms of enumeration reducibility ⋮ Enumerations of the Kolmogorov function ⋮ Complexity properties of recursively enumerable sets and \(sQ\)-completeness ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ Quasi-minimal enumeration degrees and minimal Turing degrees ⋮ Computing degrees of unsolvability ⋮ Branching in the enumeration degrees of the \(\Sigma_2^0\) sets ⋮ Definability via Kalimullin pairs in the structure of the enumeration degrees ⋮ A characterization of the δ20 hyperhyperimmune sets ⋮ Noncappable enumeration degrees below 0e′ ⋮ Point Degree Spectra of Represented Spaces ⋮ Classes bounded by incomplete sets ⋮ On \(sQ\)-completeness of recursively enumerable sets
This page was built for publication: Reducibility and Completeness for Sets of Integers
