以黑箱法加強布林函數難度之複雜度

Abstract

在高複雜度下，不同的布林函數難度與偽亂數性是等價的。然而，在NP複雜度下，它們之間的關係是很不清楚的。在本論文之前半部，我們建立mild-hardness，average-case hardness與偽亂數性在NP之下的等價性，並且說明上述概念與worst-case hardness之分野。我們主要有下列的結果：1、任何強黑箱式地從worst-case hardness加強至average-case hardness不可能在NP下實踐。2、任何強黑箱式地從worst-case hardness加強至average-case hardness需要多量額外之消息元(advice bits)。3、如能在NP複雜度下，以弱黑箱式達成從worst-case hardness加強至average-case hardness之難度加強法，其意含一NP問題類之average-case hardness。4、改進Healy等人之NP問題類之難度加強法之結果。在本論文之第二部份，我們探討難核構造之問題。我們主要有三項結果：1、任何強式黑箱式難核構造法均需要大量之詢問元(query bits)。2、任何弱式黑箱式難核構造法均需多量之消息元(advice bits)。3、弱式黑箱式難核構造法不可能在AC^0[p]下達成。

It is well-known that hardness and pseudorandomness are equivalent in high complexity class such as exponential time [NW94]. However, the relationship between various degrees of hardness and pseudorandomness is not clear in NP. In the first part of thesis, we widen the gap between worse-case hardness and average-case hardness while establishing the equivalence between average-case hardness and pseudorandomness in NP.

By using the method developed in [IL90] and [NW94], one can build the equivalence between average-case hardness and pseudorandomness within NP. On the other hand, the interplay between worse-case hardness and average-case hardness is closely related to the so-called hardness amplification which is the task of transforming a hard function f, with which any small circuit disagrees on $\delta$ fraction of the input, into a harder function f', with which any small circuit disagrees on $\epsilon$ fraction of the input where $\eps>\delta$. To separate worse-case hardness and average-case hardness in NP, we study the complexity of hardness amplification procedures. Our results include the following.

# No strongly black-box hardness amplification from hardness $(1-\delta)/2$ to $(1-\delta^k)/2$ can be realized in ATIME(O(1),k^{o(1)}). As a result, for $k=n^{\omega(1)}$, such hardness amplification cannot be carried out in NP. Therefore, such hardness amplification in general requires a high complexity.

# We show that even without any restriction on the complexity of the amplification procedure, such a strongly black-box hardness amplification must be inherently non-uniform in the following sense. To guarantee the hardness of the resulting function f', even against uniform machines, one has to start with a function f which is hard against non-uniform algorithms with $\Omega(k\log(1/\delta))$ bits of advice.

# From worst-case hardness to average-case hardness, we consider a weaker class of hardness amplifications called weakly black-box hardness amplification. First, we show that if an amplification procedure in $\NP$ can amplify hardness beyond a polynomial factor, then it must embed in itself a hard function computable in NP. As a result, it is impossible to have such a hardness amplification with hardness measured against NP/poly.

# We consider the task of transforming non-negligible hardness to average-case hardness for the complexity class NP. We show that if there is a balanced function in NP such that any circuit of size $s(n)=2^{\Omega(n)}$ fails to compute it on a $1/\poly(n)$ fraction of inputs, then there is a function in NP such that any circuit of size $s'(n)$ fails to compute it on a $1/2-1/s'(n)$ fraction of inputs, with $s'(n)=2^{\Omega(n^{2/3})}$. This improves the result of Healy et al. (STOC'04), which only achieves $s'(n)=2^{\Omega(n^{1/2})}$ for the case with $s(n)=2^{\Omega(n)}$.

In the second part of this thesis, we study a fundamental result of Impagliazzo (FOCS'95) known as the hard-core set lemma. Consider any function f which is `mildly-hard', in the sense that any circuit of size s must disagree with f on some $\delta$ fraction of inputs. Then the hard-core lemma says that f must have a hard-core set H of density $\delta$ on which it is `extremely hard', in the sense that any circuit of size $s'=O(s/(\frac{1}{\eps^2}\log(\frac{1}{\eps\delta})))$ must disagree with f on at least $(1-\eps)/2$ fraction of inputs from H.

There are three issues of the lemma which we would like to address: the loss of circuit size, the need of non-uniformity, and its inapplicability to a low complexity class. We introduce two models of hard-core set constructions, a strongly black-box one and a weakly black-box one, and show that those issues are unavoidable in such models.

# We show that in any strongly black-box construction, one can only prove the hardness of a hard-core set for smaller circuits of size at most $s'=O(s/(\frac{1}{\eps^2}\log\frac{1}{\delta}))$.

# We show that any weakly black-box construction must be inherently non-uniform --- to have a hard-core set for a class G of functions, we need to start from the assumption that f is hard against a non-uniform complexity class with $\Omega(\frac{1}{\eps}\log|G|)$ bits of advice.

# We show that weakly black-box constructions in general cannot be realized in a low-level complexity class such as AC^0[p] --- the assumption that f is hard for AC^0[p] is not sufficient to guarantee the existence of a hard-core set.