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
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
