TR06-071 Authors: John Hitchcock, A. Pavan

Publication: 31st May 2006 20:21

Downloads: 2250

Keywords:

We consider hypotheses about nondeterministic computation that

have been studied in different contexts and shown to have interesting

consequences:

1. The measure hypothesis: NP does not have p-measure 0.

2. The pseudo-NP hypothesis: there is an NP language that can be

distinguished from any DTIME(2^n^epsilon) language by an NP refuter.

3. The NP-machine hypothesis: there is an NP machine accepting 0* for

which no 2^n^epsilon-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.