Strong reducibilities
From MaRDI portal
elementary equivalencem-degreesone-degreesPost's problemsingle degreessurveyT-completenesstt- degreestt-reducibilityundecidability
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) Undecidability and degrees of sets of sentences (03D35)
Cites work
- A note on universal sets
- A recursively enumerable degree which will not split over all lesser ones
- A Theorem on Hypersimple Sets
- A Theorem on Intermediate Reducibilities
- Axiomatizable theories with few axiomatizable extensions
- Borel determinacy
- Countable initial segments of the degrees of unsolvability
- Degrees in Which the Recursive Sets are Uniformly Recursive
- Effective content of field theory
- Effectively extensible theories
- Hereditary sets and tabular reducibility
- scientific article; zbMATH DE number 3728252 (Why is no real title available?)
- scientific article; zbMATH DE number 3532932 (Why is no real title available?)
- scientific article; zbMATH DE number 3553483 (Why is no real title available?)
- scientific article; zbMATH DE number 3554279 (Why is no real title available?)
- scientific article; zbMATH DE number 3577197 (Why is no real title available?)
- scientific article; zbMATH DE number 3601575 (Why is no real title available?)
- scientific article; zbMATH DE number 3604878 (Why is no real title available?)
- scientific article; zbMATH DE number 3619321 (Why is no real title available?)
- scientific article; zbMATH DE number 3623541 (Why is no real title available?)
- scientific article; zbMATH DE number 3316928 (Why is no real title available?)
- Hypersimple sets with retraceable complements
- Initial Segments of Many-One Degrees
- Initial segments of one-one degrees
- Linear orderings under one-one reducibility
- m-powers of simple sets
- On degrees of recursively enumerable sets
- On the congruence of the upper semilattices of recursively enumerable m- powers and tabular powers
- On the Degrees of Index Sets
- On the Degrees of Index Sets. II
- On the First Order Theory of the Arithmetical Degrees
- On the Structure of Polynomial Time Reducibility
- One class of partial sets
- Post's problem and his hypersimple set
- Recursive analysis
- Recursively enumerable sets and degrees
- Recursively enumerable sets of positive integers and their decision problems
- Relationships Between Reducibilities
- Semirecursive Sets and Positive Reducibility
- Solution to a Problem of Spector
- Tabular powers of maximal sets
- The computational complexity of logical theories
- The Degrees of Hyperimmune Sets
- The weak truth table degrees of recursively enumerable sets
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
- Three theorems on the degrees of recursively enumerable sets
- Turing degrees and many-one degrees of maximal sets
- Undecidable and creative theories
- w tt-Complete Sets are not Necessarily tt-Complete
Cited in
(37)- Ershov hierarchy
- Structural interactions of the recursively enumerable T- and W-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
- Tabular degrees in \(\alpha\)-recursion theory
- Cappable recursively enumerable degrees and Post's program
- Recursive versus recursively enumerable binary relations
- The structure of the honest polynomial m-degrees
- A problem of Odifreddi
- Interpreting true arithmetic in the theory of the r.e. truth table degrees
- On 1-degrees inside m-degrees
- Where join preservation fails in the bounded Turing degrees of c.e. sets
- Lattice Embeddings in the Recursively Enumerable Truth Table Degrees
- Embedding the Diamond Lattice in the Recursively Enumerable Truth-Table Degrees
- Kleene index sets and functional m-degrees
- The index set {e: We ≡1X}.
- Recursively enumerable m- and tt-degrees. I: The quantity of m-degrees
- T-Degrees, Jump Classes, and Strong Reducibilities
- Two Theorems on Truth Table Degrees
- Index Sets and Boolean Operations
- 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′
- Contiguity and distributivity in the enumerable Turing degrees
- Degree theoretic definitions of the low2 recursively enumerable sets
- 1998–99 Annual Meeting of the Association for Symbolic Logic
- Minimal weak truth table degrees and computably enumerable Turing degrees
- Undecidability and initial segments of the (r.e.) tt-degrees
- Maximal r.e. equivalence relations
- Degrees of sets having no subsets of higher m- and t t-degree
- Reducibility by means of almost polynomial functions
- On quasi-reducibility for c.e. sets. I: The structure of the Q-degrees and the sQ-degrees
- Conjunctive degrees and cylinders
- On the complexity-relativized strong reducibilities
- Honest polynomial time reducibilities and the \(P=?NP\) problem
This page was built for publication: Strong reducibilities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3942949)
