We study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower complexity class such as NP or sub-exponential time, the existence of such an amplification procedure remains unclear.We consider a class of hardness amplifications called weakly black-box hardness amplification, in which the initial hard function is only used as a black box to construct the harder function. We show that if an amplification procedure in TIME(t) can amplify hardness beyond an O(t) factor, then it must basically embed in itself a hard function computable in TIME(t). As a result, it is impossible to have such a hardness amplification with hardness measured against TIME(t). Furthermore, we show that, for any k∈□, if an amplification procedure in Σ k P can amplify hardness beyond a polynomial factor, then it must basically embed a hard function in Σ k P. This in turn implies the impossibility of having such hardness amplification with hardness measured against Σ k P/poly.
展开▼
