Reducibility classes of P-selective sets

DOI10.1016/0304-3975(96)00094-1MaRDI QIDQ672155zbMATH OpenOpenAlexFDO

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

Publication date 27 February 1997

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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)

Recommendations

• On sets Turing reducible to p-selective sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• \(p\)-selective self-reducible sets: a new characterization of P
• P-selectivity: Intersections and indices
• On sets bounded truth-table reducible to $P$-selective sets

Cites work

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

Cited in

(14)

• scientific article; zbMATH DE number 1543037 (Why is no real title available?)
• scientific article; zbMATH DE number 1543295 (Why is no real title available?)
• The complexity of finding top-Toda-equivalence-class members
• One query reducibilities between partial information classes
• Mathematical Foundations of Computer Science 2004
• Query complexity of membership comparable sets.
• SOFSEM 2006: Theory and Practice of Computer Science
• Polynomial-Time Membership Comparable Sets
• \(p\)-Selective sets and reducing search to decision vs. self-reducibility
• \(p\)-selective self-reducible sets: a new characterization of P
• scientific article; zbMATH DE number 1848275 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• On sets Turing reducible to p-selective sets
• A note on P-selective sets and closeness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672155)