\(p\)-Selective sets and reducing search to decision vs. self-reducibility
From MaRDI portal
Publication:1816728
DOI10.1006/jcss.1996.0061zbMath0859.68055OpenAlexW2173911363MaRDI QIDQ1816728
Edith Hemaspaandra, Ashish V. Naik, Selman, Alan L., Ogihara, Mitsunori
Publication date: 31 March 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1996.0061
Related Items
Reductions between disjoint NP-pairs, Polynomial-time axioms of choice and polynomial-time cardinality, On membership comparable sets, ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, Reducibility classes of P-selective sets, Optimal advice, Collapsing and separating completeness notions under average-case and worst-case hypotheses, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions