On sets bounded truth-table reducible to $P$-selective sets
From MaRDI portal
Publication:4717049
DOI10.1051/ita/1996300201351zbMath0860.68050OpenAlexW1619951544MaRDI QIDQ4717049
Osamu Watanabe, Seinosuke Toda, Thomas Thierauf
Publication date: 13 April 1997
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92529
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing functions with parallel queries to NP
- Turing machines that take advice
- On self-reducibility and weak P-selectivity
- NP is as easy as detecting unique solutions
- 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
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- On reductions of NP sets to sparse sets
- Approximable sets
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- The complexity of promise problems with applications to public-key cryptography
- 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
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Semirecursive Sets and Positive Reducibility
This page was built for publication: On sets bounded truth-table reducible to $P$-selective sets
