Strong reducibilities

DOI10.1090/S0273-0979-1981-14863-1zbMath0484.03024OpenAlexW4246936007MaRDI QIDQ3942949

Piergiorgio Odifreddi

Publication date: 1981

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-1981-14863-1

zbMATH Keywords

surveyundecidabilityelementary equivalencePost's problemm-degreestt-reducibilityT-completenessone-degreessingle degreestt- degrees

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Embedding the Diamond Lattice in the Recursively Enumerable Truth-Table Degrees ⋮ Structural interactions of the recursively enumerable T- and W-degrees ⋮ The structure of the honest polynomial m-degrees ⋮ Intervals and sublattices of the r.e. weak truth table degrees. I: Density ⋮ Classification of degree classes associated with r.e. subspaces ⋮ Recursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degrees ⋮ A note on complete problems for complexity classes ⋮ Lattice Embeddings in the Recursively Enumerable Truth Table Degrees ⋮ Interpreting true arithmetic in the theory of the r.e. truth table degrees ⋮ Where join preservation fails in the bounded Turing degrees of c.e. sets ⋮ The index set {e: W_e ≡₁X}. ⋮ Recursively enumerable m- and tt-degrees. I: The quantity of m-degrees ⋮ The theory of the recursively enumerable weak truth-table degrees is undecidable ⋮ 1-reducibility inside an m-degree with a maximal set ⋮ Embedding lattices into the wtt-degrees below 0′ ⋮ Degree theoretic definitions of the low₂ recursively enumerable sets ⋮ Reducibility by means of almost polynomial functions ⋮ Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ Index Sets and Boolean Operations ⋮ Tabular degrees in \(\alpha\)-recursion theory ⋮ Contiguity and distributivity in the enumerable Turing degrees ⋮ Kleene index sets and functional m-degrees ⋮ Maximal r.e. equivalence relations ⋮ 1998–99 Annual Meeting of the Association for Symbolic Logic ⋮ Undecidability and initial segments of the (r.e.) tt-degrees ⋮ T-Degrees, Jump Classes, and Strong Reducibilities ⋮ On \(1\)-degrees inside \(m\)-degrees ⋮ A problem of Odifreddi ⋮ Two Theorems on Truth Table Degrees ⋮ Degrees of sets having no subsets of higher m- and t t-degree ⋮ On the complexity-relativized strong reducibilities ⋮ Cappable recursively enumerable degrees and Post's program ⋮ Recursive versus recursively enumerable binary relations ⋮ Ershov hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Borel determinacy
• On the congruence of the upper semilattices of recursively enumerable m- powers and tabular powers
• Tabular powers of maximal sets
• One class of partial sets
• The computational complexity of logical theories
• Hereditary sets and tabular reducibility
• m-powers of simple sets
• On degrees of recursively enumerable sets
• Three theorems on the degrees of recursively enumerable sets
• Initial segments of one-one degrees
• Recursive analysis
• Hypersimple sets with retraceable complements
• Solution to a Problem of Spector
• On the First Order Theory of the Arithmetical Degrees
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Undecidable and creative theories
• Effective content of field theory
• A Theorem on Intermediate Reducibilities
• w tt-Complete Sets are not Necessarily tt-Complete
• On the Structure of Polynomial Time Reducibility
• The weak truth table degrees of recursively enumerable sets
• A recursively enumerable degree which will not split over all lesser ones
• Countable initial segments of the degrees of unsolvability
• Recursively enumerable sets and degrees
• Post's problem and his hypersimple set
• On the Degrees of Index Sets
• Linear orderings under one-one reducibility
• Effectively extensible theories
• On the Degrees of Index Sets. II
• Relationships Between Reducibilities
• Semirecursive Sets and Positive Reducibility
• Turing degrees and many-one degrees of maximal sets
• Axiomatizable theories with few axiomatizable extensions
• The Degrees of Hyperimmune Sets
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Initial Segments of Many-One Degrees
• A note on universal sets
• A Theorem on Hypersimple Sets
• Recursively enumerable sets of positive integers and their decision problems