Semirecursive Sets and Positive Reducibility
From MaRDI portal
Publication:5595155
DOI10.2307/1994957zbMath0198.32402OpenAlexW4232819959MaRDI QIDQ5595155
Publication date: 1968
Full work available at URL: https://doi.org/10.2307/1994957
Related Items (96)
e- and s-degrees ⋮ A class of hypersimple incomplete sets ⋮ Embedding the Diamond Lattice in the Recursively Enumerable Truth-Table Degrees ⋮ Generalized notions of mind change complexity ⋮ A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ NP-hard sets are superterse unless NP is small ⋮ On polynomially D verbose sets ⋮ Enumeration 1-genericity in the local enumeration degrees ⋮ The automorphism group of the enumeration degrees ⋮ Degrees of denumerability reducibilities ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ Strong enumeration reducibilities ⋮ Polynomial terse sets ⋮ On multiple positive reducibility ⋮ RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS ⋮ Relations between certain reducibilities ⋮ One strengthening of \(Q\)-reducibility ⋮ Logic and probabilistic systems ⋮ Unnamed Item ⋮ Deficiency Sets and Bounded Information Reducibilities ⋮ A STRUCTURAL DICHOTOMY IN THE ENUMERATION DEGREES ⋮ Nondeterministic bounded query reducibilities ⋮ Time bounded frequency computations ⋮ Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility ⋮ Three theorems on tt-degrees ⋮ s-Degrees within e-Degrees ⋮ Turing degrees of hypersimple relations on computable structures ⋮ Dimension and the structure of complexity classes ⋮ Reducibilities among equivalence relations induced by recursively enumerable structures ⋮ Badness and jump inversion in the enumeration degrees ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ Cupping Classes of $\Sigma^0_2$ Enumeration Degrees ⋮ Iterative learning from texts and counterexamples using additional information ⋮ Computability of graphs ⋮ Lower semilattices of separable congruences of numbered algebras ⋮ Reducibility by Zhegalkin-linear tables ⋮ tt-degrees of recursively enumerable Turing degrees. II ⋮ Closed left-r.e. sets ⋮ Relationships Between Reducibilities ⋮ Enumeration Reducibility and Computable Structure Theory ⋮ Lowness, Randomness, and Computable Analysis ⋮ Polynomial clone reducibility ⋮ Property of t-retraceability and automorphisms of the lattice of recursively enumerable sets ⋮ \(sQ_1\)-degrees of computably enumerable sets ⋮ Some observations on NP real numbers and P-selective sets ⋮ Reductions on NP and p-selective sets ⋮ Avoiding uniformity in the \(\Delta_2^0\) enumeration degrees ⋮ Cupping and definability in the local structure of the enumeration degrees ⋮ Almost semirecursive sets ⋮ Some reducibilities and splittings of recursively enumerable sets ⋮ Some effects of Ash-Nerode and other decidability conditions on degree spectra ⋮ Branching in the \({\Sigma^0_2}\)-enumeration degrees: a new perspective ⋮ 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 ⋮ The automorphism group and definability of the jump operator in the \(\omega\)-enumeration degrees ⋮ On sets Turing reducible to p-selective sets ⋮ Densely simple sets with retraceable complements ⋮ Structural properties of \(Q\)-degrees of n-c.e. sets ⋮ Weakly computable real numbers ⋮ The \(n\)-rea enumeration degrees are dense ⋮ Countable thin \(\Pi^0_1\) classes ⋮ Weakly semirecursive sets and r.e. orderings ⋮ On Kalimullin pairs ⋮ Defining totality in the enumeration degrees ⋮ On computably enumerable structures ⋮ btt-reducibility ⋮ The limitations of cupping in the local structure of the enumeration degrees ⋮ tt- and m-degrees ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Goodness in the enumeration and singleton degrees ⋮ On the congruence of the upper semilattices of recursively enumerable m- powers and tabular powers ⋮ Inductive definability in formal language theory ⋮ Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets ⋮ One class of partial sets ⋮ e-powers of hyperimmune retraceable sets ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP ⋮ Classes of recursively enumerable sets and Q-reducibility ⋮ Hypersimple sets with retraceable complements ⋮ Turing degrees of certain isomorphic images of computable relations ⋮ Computably enumerable sets and quasi-reducibility ⋮ Definability via Kalimullin pairs in the structure of the enumeration degrees ⋮ Hereditary sets and tabular reducibility ⋮ Limited-combinatorial sets ⋮ Hypersimplicity and semicomputability in the weak truth table degrees ⋮ Strong reducibilities ⋮ Recursive-combinatorial properties of subsets of the natural numbers ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets ⋮ Graphs realised by r.e. equivalence relations ⋮ Classes bounded by incomplete sets ⋮ Weak combinatorial selective properties of subsets of the natural numbers ⋮ Upper semilattice of recursively enumerable Q-degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Three theorems on the degrees of recursively enumerable sets
- A note on pseudo-creative sets and cylinders
- The minimum of two regressive isols
- Retraceable Sets
- Recursively Enumerable Sets and Retracing Functions
- Degrees of Unsolvability. (AM-55)
- Some Notions of Reducibility and Productiveness
- Effectively Simple Sets
- On Properties of Regressive Sets
- There exist two regressive sets whose intersection is not regressive
- On a Class of Complete Simple Sets
- Completeness, the Recursion Theorem, and Effectively Simple Sets
- The Degrees of Hyperimmune Sets
- A Theorem on Hypersimple Sets
- Recursively enumerable sets of positive integers and their decision problems
This page was built for publication: Semirecursive Sets and Positive Reducibility
