The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim’s hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some ε > 0, if there is a language in E which requires nondeterministic circuits of size 2^{ε n} , then P = BPP. This differs from Impagliazzo and Wigderson’s theorem “only” by replacing deterministic circuits with nondeterministic ones.