**Title:** Approximable Sets
**Authors:** Richard Beigel, Martin Kummer, and Frank Stephan

**Abstract:**
Much structural work on NP-complete sets has exploited SAT's
d-self-reducibility. In this paper we exploit the additional fact
that SAT is a d-cylinder to show that NP-complete sets are
p-superterse unless P = NP. In fact, every set that is
NP-hard under polynomial-time *n*^{o(1)}-tt reductions is
p-superterse unless P = NP. In particular no p-selective
set is NP-hard under polynomial-time *n*^{o(1)}-tt
reductions unless P = NP. In addition, no easily
countable set is NP-hard under Turing reductions unless P =
NP. Self-reducibility does not seem to suffice for our main
result: in a relativized world, we construct a d-self-reducible set in
NP - P that is polynomial-time 2-tt reducible to a p-selective set.

Download Full Paper