We show that
derandomizing polynomial identity testing over an arbitrary finite
field implies that NEXP does not have polynomial size boolean
circuits. In other words, for any finite field F(q) of size q,
$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where
$PIT_q$ is the polynomial identity testing problem over F(q), and
NSUBEXP is the nondeterministic subexpoential time class of
languages. Our result is in contract to Kabanets and Impagliazzo's
existing theorem that derandomizing the polynomial identity testing
in the integer ring Z implies that NEXP does have polynomial
size boolean circuits or permanent over Z does not have polynomial
size arithmetic circuits.
We show that
derandomizing polynomial identity testing over an arbitrary finite
field implies that NEXP does not have polynomial size boolean
circuits. In other words, for any finite field F(q) of size q,
$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where
$PIT_q$ is the polynomial identity testing problem over F(q), and
NSUBEXP is the nondeterministic subexpoential time class of
languages. Our result is in contract to Kabanets and Impagliazzo's
existing theorem that derandomizing the polynomial identity testing
in the integer ring Z implies that NEXP does have polynomial
size boolean circuits or permanent over Z does not have polynomial
size arithmetic circuits.
Two notions of polynomial identity testing
are defined. Their difference and connection
are compared.
