Polynomial Time Reducibility to a Set of Small Density: (Extended Abstract)
Osamu Watanabe · 1987
There are several ways to show "difficulty" of a given set of strings. In this paper we take the following approach: we estimate the intractability of a given set L in terms of the density of a set to which L is polynomial time reducible. Intractability of sets in UP (⊆ NP) and EXP (= Uc>0DTIME(2cn)) are studied from this point of view. We show that (i) if Ρ ≠ UP, then there exists a set in UP which is ≤$_\text{m}^\text{p}$-reducible to no sparse sets; and that (ii) for each one of ≤$_\text{btt}^\text{p}$-, ≤$_\text{c}^\text{p}$and ≤$_\text{d}^\text{p}$-reduction types, there respectively exists a set in EXP which is reducible to no sets of less than exponential density via this type of reductions. Implications of these results are also considered. We show that (i) a hard one-way function (i.e., a oneway function which has no feasible approximations for its inverse) exists if one-way functions exist at all, and (ii) some set in EXP has no polynomial time approximation algorithms.