Some results on selectivity and self-reducibility
From MaRDI portal
Publication:672402
DOI10.1016/0020-0190(95)00073-LzbMath0875.68423MaRDI QIDQ672402
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Cites Work
- Unnamed Item
- On self-reducibility and weak P-selectivity
- Strong nondeterministic polynomial-time reducibilities
- Some observations on NP real numbers and P-selective sets
- Reductions on NP and p-selective sets
- PP is closed under truth-table reductions
- Adaptive versus nonadaptive queries to NP and P-selective sets
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Polynomial-Time Membership Comparable Sets
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Semirecursive Sets and Positive Reducibility
