Abstract:
We consider hypotheses about nondeterministic computation that
have been studied in different contexts and shown to have interesting
consequences:
The measure hypothesis: NP does not have p-measure 0.
The pseudo-NP hypothesis: there is an NP language
that can be distinguished from any DTIME(2nε)
language by an NP refuter.
The NP-machine hypothesis: there is an NP machine
accepting 0* for which no
2nε-time machine can find infinitely
many accepting computations.
We show that the NP-machine hypothesis is implied by each of the first
two. Previously, no relationships were known among these three
hypotheses. Moreover, we unify previous work by showing that several
derandomizations and circuit-size lower bounds that are known to
follow from the first two hypotheses also follow from the NP-machine
hypothesis. In particular, the NP-machine hypothesis becomes the
weakest known uniform hardness hypothesis that derandomizes AM. We
also consider UP versions of the above hypotheses as well as related
immunity and scaled dimension hypotheses.