Semirecursive Sets and Positive Reducibility
From MaRDI portal
Cites work
- A note on pseudo-creative sets and cylinders
- A Theorem on Hypersimple Sets
- Completeness, the Recursion Theorem, and Effectively Simple Sets
- Degrees of Unsolvability. (AM-55)
- Effectively Simple Sets
- scientific article; zbMATH DE number 3273186 (Why is no real title available?)
- scientific article; zbMATH DE number 3394122 (Why is no real title available?)
- On a Class of Complete Simple Sets
- On Properties of Regressive Sets
- Recursively Enumerable Sets and Retracing Functions
- Recursively enumerable sets of positive integers and their decision problems
- Retraceable Sets
- Some Notions of Reducibility and Productiveness
- The Degrees of Hyperimmune Sets
- The minimum of two regressive isols
- There exist two regressive sets whose intersection is not regressive
- Three theorems on the degrees of recursively enumerable sets
Cited in
(only showing first 100 items - show all)- Upper semilattice of recursively enumerable Q-degrees
- e- and s-degrees
- A class of hypersimple incomplete sets
- Degrees of denumerability reducibilities
- Polynomial terse sets
- Nondeterministic bounded query reducibilities
- Three theorems on tt-degrees
- Reducibility by Zhegalkin-linear tables
- tt-degrees of recursively enumerable Turing degrees. II
- Some observations on NP real numbers and P-selective sets
- Reductions on NP and p-selective sets
- Some effects of Ash-Nerode and other decidability conditions on degree spectra
- Densely simple sets with retraceable complements
- The \(n\)-rea enumeration degrees are dense
- Countable thin ^0_1 classes
- Weakly semirecursive sets and r.e. orderings
- btt-reducibility
- tt- and m-degrees
- On the congruence of the upper semilattices of recursively enumerable m- powers and tabular powers
- Inductive definability in formal language theory
- One class of partial sets
- e-powers of hyperimmune retraceable sets
- Turing degrees of certain isomorphic images of computable relations
- Computably enumerable sets and quasi-reducibility
- On symmetric differences of NP-hard sets with weakly P-selective sets
- Quasi-linear truth-table reductions to \(p\)-selective sets
- Time bounded frequency computations
- Turing degrees of hypersimple relations on computable structures
- Classes bounded by incomplete sets
- Enumeration 1-genericity in the local enumeration degrees
- Positive presentations of families in relation to reducibility with respect to enumerability
- p-selective self-reducible sets: a new characterization of P
- Classes of recursively enumerable sets and Q-reducibility
- Hereditary sets and tabular reducibility
- Generalized notions of mind change complexity
- On multiple positive reducibility
- Relations between certain reducibilities
- One strengthening of \(Q\)-reducibility
- Logic and probabilistic systems
- Almost semirecursive sets
- Some reducibilities and splittings of recursively enumerable sets
- The automorphism group and definability of the jump operator in the \(\omega\)-enumeration degrees
- On computably enumerable structures
- The limitations of cupping in the local structure of the enumeration degrees
- Limited-combinatorial sets
- Graphs realised by r.e. equivalence relations
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- Polynomial clone reducibility
- Avoiding uniformity in the \(\Delta_2^0\) enumeration degrees
- Hypersimple sets with retraceable complements
- Hypersimplicity and semicomputability in the weak truth table degrees
- The automorphism group of the enumeration degrees
- sQ₁-degrees of computably enumerable sets
- Semilinear sets and counter machines: a brief survey
- NP-hard sets are superterse unless NP is small
- Fixed-parameter decidability: extending parameterized complexity analysis
- Closed left-r.e. sets
- Enumeration reducibility and computable structure theory
- Lowness, Randomness, and Computable Analysis
- Embedding the Diamond Lattice in the Recursively Enumerable Truth-Table Degrees
- s-Degrees within e-Degrees
- Cupping Classes of $\Sigma^0_2$ Enumeration Degrees
- Monotone reducibility and the family of infinite sets
- Deficiency Sets and Bounded Information Reducibilities
- Strong reducibilities
- Badness and jump inversion in the enumeration degrees
- Iterative learning from texts and counterexamples using additional information
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- On sets bounded truth-table reducible to P-selective sets
- Positive set‐operators of low complexity
- On polynomially \(\mathcal{D}\)-verbose sets
- Relationships between computability-theoretic properties of problems
- A structural dichotomy in the enumeration degrees
- Computability of graphs
- scientific article; zbMATH DE number 7092351 (Why is no real title available?)
- Definability via Kalimullin pairs in the structure of the enumeration degrees
- Cupping and definability in the local structure of the enumeration degrees
- scientific article; zbMATH DE number 5062001 (Why is no real title available?)
- Relationships Between Reducibilities
- On Kalimullin pairs
- Defining totality in the enumeration degrees
- Weakly computable real numbers
- The communication complexity of enumeration, elimination, and selection
- Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets
- Dimension and the structure of complexity classes
- Lower semilattices of separable congruences of numbered algebras
- Limited combinatorial-selector sets
- Frequency computation and bounded queries
- Reducibility classes of P-selective sets
- Some results on selectivity and self-reducibility
- P-selectivity: Intersections and indices
- A note on P-selective sets and closeness
- On sets Turing reducible to p-selective sets
- On quasi-reducibility for c.e. sets. I: The structure of the Q-degrees and the sQ-degrees
- Finite logical specifications of effectively separable data models
- Non-empty open intervals of computably enumerable sQ₁-degrees
- Choosing, agreeing, and eliminating in communication complexity
- Recursive-combinatorial properties of subsets of the natural numbers
- Weak combinatorial selective properties of subsets of the natural numbers
- Strong enumeration reducibilities
This page was built for publication: Semirecursive Sets and Positive Reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5595155)
