On sets Turing reducible to p-selective sets

DOI10.1007/BF02679445zbMath0874.68128OpenAlexW2017208079MaRDI QIDQ675861

Juan-Miguel Gracia

Publication date: 10 November 1997

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02679445

zbMATH Keywords

Turing reducibility

Mathematics Subject Classification ID

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

Related Items (4)

Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Query complexity of membership comparable sets. ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ Optimal advice

Cites Work

• Unnamed Item
• Reducibility classes of P-selective sets
• Optimal advice
• On self-reducibility and weak P-selectivity
• Relativized circuit complexity
• Logarithmic advice classes
• 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
• Semirecursive Sets and Positive Reducibility

This page was built for publication: On sets Turing reducible to p-selective sets