Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
From MaRDI portal
Publication:4739905
DOI10.1016/S0019-9958(82)80084-3zbMath0504.03022MaRDI QIDQ4739905
Publication date: 1982
Published in: Information and Control (Search for Journal in Brave)
Related Items
A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, On polynomially D verbose sets, On helping by robust oracle machines, Geometric optimization and the polynomial hierarchy, Polynomial terse sets, Geometric optimization and \(D^ P\)-completeness, Promise problems complete for complexity classes, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, A result relating disjunctive self-reducibility to P-immunity, Recursion-theoretic ranking and compression, Some connections between bounded query classes and non-uniform complexity., On sets polynomially enumerable by iteration, The Power of Self-Reducibility: Selectivity, Information, and Approximation, Some results on selectivity and self-reducibility, P-selectivity: Intersections and indices, Sparse selfreducible sets and nonuniform lower bounds, The communication complexity of enumeration, elimination, and selection, Choosing, agreeing, and eliminating in communication complexity, On sets bounded truth-table reducible to $P$-selective sets, On the size of classes with weak membership properties
