\(p\)-Selective sets and reducing search to decision vs. self-reducibility

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

zbMATH Keywords

self-reducibilitytally language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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