Quasi-linear truth-table reductions to \(p\)-selective sets

DOI10.1016/0304-3975(95)00167-0zbMath0871.68082OpenAlexW2078835786MaRDI QIDQ1351469

V. Arvind, Manindra Agrawal

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(95)00167-0

Mathematics Subject Classification ID

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

Related Items

Query complexity of membership comparable sets. ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Frequency computation and bounded queries ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Commutative queries ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph

Cites Work

• Unnamed Item
• Turing machines that take advice
• On self-reducibility and weak P-selectivity
• Some observations on NP real numbers and P-selective sets
• Reductions on NP and p-selective sets
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• A comparison of polynomial time reducibilities
• Self-reducibility
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Polynomial-Time Membership Comparable Sets
• Semirecursive Sets and Positive Reducibility