Pseudo-random generators and structure of complete degrees

Abstract

It is shown that, if there exist sets in E (the exponential complexity class) that require 2^Ω(n)-sized circuits, then sets that are hard for class P (the polynomial complexity class) and above, under 1-1 reductions, are also hard under 1-1 size-increasing reductions. Under the assumption of the hardness of solving the RSA (Rivest-Shamir-Adleman, 1978) problem or the discrete log problem, it is shown that sets that are hard for class NP (nondeterministic polynomial) and above, under many-1 reductions, are also hard under (non-uniform) 1-1 and size-increasing reductions.