Reducibility classes of P-selective sets

DOI10.1016/0304-3975(96)00094-1zbMATH Open0872.68043OpenAlexW2086454198MaRDI QIDQ672155FDOQ672155

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

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

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

zbMATH Keywords

reducibilityP-selective sets

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 self-reducible sets: a new characterization of P
• Title not available (Why is that?)
• 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)