On sets Turing reducible to p-selective sets

DOI10.1007/BF02679445zbMATH Open0874.68128OpenAlexW2017208079MaRDI QIDQ675861FDOQ675861

Authors: 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

Recommendations

• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Reducibility classes of P-selective sets
• On sets bounded truth-table reducible to $P$-selective sets
• Publication:4942650

zbMATH Keywords

Turing reducibility

Mathematics Subject Classification ID

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

Cites Work

• Relativized circuit complexity
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Title not available (Why is that?)
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Semirecursive Sets and Positive Reducibility
• On self-reducibility and weak P-selectivity
• Logarithmic advice classes
• Reducibility classes of P-selective sets
• Optimal advice

Cited In (11)

• Title not available (Why is that?)
• Separating NE from Some Nonuniform Nondeterministic Complexity Classes
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Query complexity of membership comparable sets.
• \(p\)-selective self-reducible sets: a new characterization of P
• Title not available (Why is that?)
• With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
• Separating NE from some nonuniform nondeterministic complexity classes
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Reducibility classes of P-selective sets
• Optimal advice

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

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