Hardness of Sparse Sets and Minimal Circuit Size Problem

Comparing with some existing results about sparse sets hardness magnification in this line [4], there are some new advancements in this paper.

1. 1.

   Our magnification of sparse set is based on a uniform streaming model. A class of results in [4] are based on nonuniform models. In [10], they show that if there is $A\in{\rm PH}$, and a function $s(n)\geq\log n$, search-${\rm MCSP}^{A}[s(n)]$ does not have $s(n)^{c}$ updating time in deterministic streaming model for all positive, then ${\rm P}\not={\rm NP}$. ${\rm MCSP}[s(n)]$ is a $s(n)^{{\rm O}(s(n))}$-sparse set.

2. 2.

   Our method is conceptually simple, and easy to understand. It is a polynomial algebraic approach on finite fields.

3. 3.

   A flexible trade off between sparseness and time complexity is given in our paper.

Proving NP-hardness for MCSP implies ${\rm EXP}\not={\rm ZPP}$ [8, 11]. We consider the implication of ZPP-hardness for ${\rm MCSP}$, and show that if MCSP is ${\rm ZPP}\cap{\rm TALLY}(d(n),g(n))$-hard for a function pair such as $d(n)=\log\log n$ and $g(n)=2^{2^{2n}}$, then ${\rm EXP}\not={\rm ZPP}$. It seems that proving MCSP is ${\rm ZPP}$-hard is much easier than proving MCSP is NP-hard since ${\rm ZPP}\subseteq({\rm NP}\cap{{\rm co}{\rm\mbox{-}}{\rm NP}})\subseteq{\rm NP}$. According to the low-high hierarchy theory developed by Schöning [14], the class ${\rm NP}\cap{{\rm co}{\rm\mbox{-}}{\rm NP}}$ is the low class $L_{1}$. Although ${\rm MCSP}$ may not be in the class ${\rm ZPP}$, it is possible to be ${\rm ZPP}$-hard.

We have a polynomial method over finite fields. Let $L$ be $f(n)$-sparse language in ${\rm NTIME}(t_{1}(n))$. In order to handle an input string of size $n$, a finite field $F={\rm GF}(q)$ with $q=2^{k}$ for some integer $k$ is selected, and is represented by $R(F)=(2,t_{F}(z))$, where $t_{F}(z)$ is a irreducible polynomial over ${\rm GF}(2)$. An input $y=a_{1}a_{2}\cdots a_{n}$ is partitioned into $k$-segments $s_{r-1}\cdots s_{1}s_{0}$ such that each $s_{i}$ is converted into an element $w(s_{i},u)$ in $F$, and $y$ is transformed into an polynomial $d_{y}(z)=z^{r}+\sum_{i=0}^{r-1}w(s_{i},u)z^{i}$. A random element $a\in F$ is chosen in the beginning of streaming algorithm before processing the input stream. The value $d_{y}(a)$ is evaluated with the procession of input stream. The finite $F$ is large enough such that for different $y_{1}$ and $y_{2}$ of the same length, $d_{y_{1}}(.)$ and $d_{y_{2}}(.)$ are different polynomials due to their different coefficients derived from $y_{1}$ and $y_{2}$, respectively. Let $H(y)$ be the set of all $\langle n,a,d_{y}(a)\rangle$ with $a\in F$ and $n=|y|$. Set $A(n)$ is the union of all $H(y)$ with $y\in L^{n}$. The set of $A$ is $\cup_{i=1}^{\infty}A(n)$. A small lower bound for the language $A$ is magnified to large lower bound for $L$.

The size of field $F$ depends on the density of set $L$ and is ${\rm O}(f(n)n)$. By the construction of $A$, if $y\in L$, there are $q$ tuples $\langle n,a,d_{y}(a)\rangle$ in $A$ that are generated by $y$ via all $a$ in $F$. For two different $y_{1}$ and $y_{2}$ of length $n$, the intersection $H(y_{1})\cap H(y_{2})$ is bounded by the degree of $d_{y_{1}}(.)$. If $y\not\in L$, the number of items $\langle n,a,d_{y}(a)\rangle$ generated by $y$ is at most ${q\over 4}$ in $A$. If $y\in L$, the number of items $\langle n,a,d_{y}(a)\rangle$ generated by $y$ is $q$ in $A$. This enables us to convert a string $x$ of length $n$ in $L$ into some strings in $A$ of length much smaller than $n$, make the hardness magnification possible.

Our another result shows that ZPP-hardness for MCSP implies ${\rm EXP}\not={\rm ZPP}$. We identify a class of functions that are padding stable, which has the property if $T\in{\rm TALLY}(d(n),g(n))$, then $\{1^{n+2^{n}}:1^{n}\in T\}\in{\rm TALLY}(d(n),g(n))$. The function pair $d(n)=\log\log n$ and $g(n)=2^{2^{2n}}$ has this property. We construct a very sparse tally set $L\in{\rm EXP}\cap{\rm TALLY}(d(n),g(n))$ that separates ${\rm ZPEXP}$ from ${\rm ZPP}$, where ${\rm ZPEXP}$ is the zero error exponential time probabilistic class. It is based on a diagonal method that is combined with a padding design. A tally language $L$ has a zero-error $2^{2^{n}}$-time probabilistic algorithm implies $L^{\prime}=\{1^{n+2^{n}}:1^{n}\in L\}$ has a zero-error $2^{n}$-time probabilistic algorithm. Adapting to the method of [11], we prove that if MCSP is ${\rm ZPP}\cap{\rm TALLY}(d(n),g(n))$-hard under polynomial time truth-table reductions, then ${\rm EXP}\not={\rm ZPP}$.

The algorithm Streaming(.) is based on a language $L$ that is $f(n)$-sparse. It generates a field $F={\rm GF}(2^{k})$ and evaluates $d_{x}(a)$ with a random element $a$ in $F$. A polynomial $z^{r}+\sum_{i=0}^{r-1}b_{i}z^{i}=z^{r}+b_{r-1}z^{r-1}+b_{r-2}z^{r-2}+\cdots+b_{0}$ can be evaluated by $(\cdots((z+b_{r-1})z+b_{r-2})z+...)z+b_{0}$ according to the classical Horner’s algorithm. For example, $z^{2}+z+1=(z+1)z+1$.

Algorithm

Streaming($n,x$)

Input: an integer $n$, and string $x=a_{1}\cdots a_{n}$ of the length $n$;

Steps:

1. 1.

   Select a field size $q=2^{k}$ such that $8f(n)n<q\leq 16f(n)n$.

2. 2.

   Generate an irreducible polynomial $t_{F}(u)$ of degree $k$ over ${\rm GF}(2)$ such that $(2,t_{F}(u))$ represents finite $F={\rm GF}(q)$ (by Theorem 2 with $p=2$);

3. 3.

   Let $a$ be a random element in $F$;

4. 4.

   Let $r=\left\lceil n\over k\right\rceil$; (Note that $r$ is the number of $k$-segments of $x$. See Section 2)

5. 5.

   Let $j=r-1$;

6. 6.

   Let $v=1$;

7. 7.

   Repeat

8. 8.

   {

9. 9.

   Receive the next $k$-segment $s_{j}$ from the input stream $x$;

10. 10.

    Convert $s_{j}$ into an element $b_{j}=w(s_{j},u)$ in ${\rm GF}(q)$;

11. 11.

    Let $v=v\cdot a+b_{j}$;

12. 12.

    Let $j=j-1$;

    }

13. 13.

    Until $j<0$ (the end of the stream);

14. 14.

    Output $\langle n,a,v\rangle$;

End of Algorithm

Now we have our magnification algorithm. Let $M(.)$ be a randomized Turing machine to accept a language $A$ that contains all $\langle|x|,a,d_{x}(a)\rangle$ with $a\in F$ and $x\in L$. We have the following randomized streaming algorithm to accept $L$ via the randomized algorithm $M(.)$ for $A$.

Algorithm

Magnification($n,x$)

Input integer $n$ and $x=a_{1}\cdots a_{n}$ as a stream;

Steps: Let $y=$Streaming($n,x$); Accept if $M(y)$ accepts;

End of Algorithm

In this section, we derive some results about hardness magnification via sparse set. Our results show a trade off between the hardness magnification and sparseness via the streaming model.

Claim 1. For any $x\not\in L^{n}$ with $n=|x|$, we have $|H(x)\cap A(n)|<{q\over 4}$.

Claim 2. If $x\in L$, then Streaming$(|x|,x)\in A$. Otherwise, with probability at most ${1\over 4}$, Streaming$(|x|,x)\in A$.

Claim 3. $A\in{\rm NTIME}(t_{2}(m))$.

Since $L\in{\rm NTIME}(t_{1}(n))$, checking if $u\in A$ takes nondeterministic $t_{1}(n)$ steps to guess a string $x\in L^{n}$, $u_{1}(z)$ deterministic steps to generate $t_{F}(u)$ for the field $F$, $O(z)$ nondeterministic steps to generate a random element $a\in F$, and additional ${\rm O}(n\cdot u_{2}(z))$ steps to evaluate $d_{x}(a)$ in by following algorithm Streaming(.) and check $b=d_{x}(a)$. The polynomial $t_{F}(u)$ in the ${\rm GF}(2)$ has degree at most $z$. Each polynomial operation ($+$ or .) in $F$ takes at most $u_{2}(z)$ steps. Since $z+t_{1}(n)+u_{1}(z)+n\cdot u_{2}(z)\leq t_{2}(m)$ time by the condition of this theorem, we have $A\in{\rm NTIME}(t_{2}(m))$.

 

Claim 4. If $A\in{\rm BTIME}(t_{3}(m))$, then $L\in{\rm Streaming}(u_{1}(10v(n)),v(n),v(n),$ $1,t_{3}(10v(n)))$.

If $A\in{\rm BTIME}(t_{3}(m))$, then $L$ has a randomized streaming algorithm that has at most $t_{3}(10v(n))$ random steps after reading the input, and at most ${\rm O}(v(n))$ space. After reading one substring $s_{i}$ from $x$, it takes one conversion from a substring of the input to an element of field $F$ by line 10, and at most two field operations by line 11 in the algorithm Streaming(.).

 

Claim 4 brings a contradiction to our assumption about the complexity of $L$ in the theorem. This proves the theorem.         

Our Definition 7 is based Proposition 6. It can simplify the proof when we handle a function that is $n^{o(1)}$.

It is easy to see that $v(n)=n^{{\rm o}(1)}$, and both $u_{1}(n)$ and $u_{2}(n)$ are $n^{{\rm O}(1)}$ (see Theorem 2). For any fixed $c_{0}>0$, we have $t_{2}(v(n))>t_{2}(\log f(n))\geq t_{2}(n^{1\over g(n)})>t_{1}(n)+n^{c_{0}}$ for all large $n$. For all large $n$, we have

	$\displaystyle t_{3}(10v(n))$	$\displaystyle\leq$	$\displaystyle t_{3}(20\log f(n))=t_{3}(20n^{1\over g(n)})$		(1)
		$\displaystyle\leq$	$\displaystyle(20n^{1\over g(n)})^{\sqrt{g(20n^{1\over g(n)}})}\leq(n^{2\over g(n)})^{\sqrt{g(n)}}=n^{o(1)}.$		(2)

Clearly, these functions satisfy the inequality of the precondition in Theorem  5. Assume $L\in{\rm Streaming}({\rm poly}(v(n)),v(n),v(n),1,t_{3}(10v(n)))$. With $O(v(n))=n^{o(1)}$ space, we have a field representation $(2,t_{F}(.))$ with $\deg(t_{F}(.))=n^{o(1)}$. Thus, each field operation takes $n^{o(1)}$ time by the brute force method for polynomial addition and multiplication. We have $t_{3}(10v(n))=n^{o(1)}$ by inequality (2). Thus, the streaming algorithm updating time is $n^{o(1)}$. Therefore, we have that $L$ has a randomized streaming algorithm with $n^{o(1)}$ updating time, and $n^{o(1)}$ space. This gives a contradiction. So,
$L\not\in{\rm Streaming}({\rm poly}(v(n)),v(n),v(n),1,t_{3}(10v(n)))$. By Theorem 5, there is $A\in{\rm NTIME}(t_{2}(n))$ such that $A\not\in{\rm BTIME}(t_{3}(n))$. Therefore, $A\not\in{\rm BPP}$. Thus, ${\rm NEXP}\not={\rm BPP}$.