Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-071 | 25th April 2006 00:00

Hardness Hypotheses, Derandomization, and Circuit Complexity


Authors: John Hitchcock, A. Pavan
Publication: 31st May 2006 20:21
Downloads: 2996


We consider hypotheses about nondeterministic computation that
have been studied in different contexts and shown to have interesting

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

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.

ISSN 1433-8092 | Imprint