Reducibility classes of P-selective sets

DOI10.1016/0304-3975(96)00094-1zbMath0872.68043OpenAlexW2086454198MaRDI QIDQ672155

Albrecht Hoene, Ogihara, Mitsunori, Hemaspaandra, Lane A.

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(96)00094-1

zbMATH Keywords

reducibilityP-selective sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Query complexity of membership comparable sets. ⋮ On sets Turing reducible to p-selective sets ⋮ One query reducibilities between partial information classes

Cites Work

• On self-reducibility and weak P-selectivity
• Reductions on NP and p-selective sets
• Average case completeness
• A comparison of polynomial time reducibilities
• \(p\)-Selective sets and reducing search to decision vs. self-reducibility
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Near-Testable Sets
• On Sets with Efficient Implicit Membership Tests
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Complete sets and closeness to complexity classes
• Polynomial-Time Membership Comparable Sets
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• Semirecursive Sets and Positive Reducibility

This page was built for publication: Reducibility classes of P-selective sets