ECCC-Report TR02-038https://eccc.weizmann.ac.il/report/2002/038Comments and Revisions published for TR02-038en-usFri, 09 Aug 2002 00:00:00 +0300
Revision 1
| Resource Tradeoffs and Derandomization |
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2002/038#revision1We consider uniform assumptions for derandomization. We provide intuitive evidence that BPP can be simulated non-trivially in deterministic time by showing that (1) There is a simulation of P in POLYLOGSPACE that is successful against all polynomial-time adversaries infinitely often, or BPP \subseteq SUBEXP (2) There is a simulation of P in SUBPSPACE that is successful against all subexponential-time adversaries infinitely often, or BPP \subseteq P. These results complement and extend earlier work of Sipser, Nisan-Wigderson and Lu.
We show similar tradeoffs between simulation of nondeterministic time by nondeterministic space and simulation of probabilistic time by nondeterministic time.
Finally, we give uniform assumptions under which the following results hold - (1)Probabilistic polynomial time has a strict hierarchy, (2) Probabilistic time can be simulated nontrivially by probabilistic space.
Fri, 09 Aug 2002 00:00:00 +0300https://eccc.weizmann.ac.il/report/2002/038#revision1
Paper TR02-038
| Resource Tradeoffs and Derandomization |
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2002/038We consider uniform assumptions for derandomization. We provide
intuitive evidence that BPP can be simulated non-trivially in
deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE
implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP
= P. These results extend and complement earlier work of Sipser, Nisan-
Wigderson and Lu.
We show similar tradeoffs between simulations of nondeterministic time
by nondeterministic space and simulations of randomized algorithms by
nondeterministic time. These results may be helpful in settling the
question of whether BPP=NEXP. We state two conjectures under which BPP
is not equal to NEXP: (1) An infinitely often (i.o.i.) version of
Lautemann's Theorem holds (2) Every language in BPP can be reduced to
SAT using nondeterministic reductions where the entire set of queries
can be computed in nondeterministic polynomial time from the input.
Unlike previous approaches, our approach does not seem to require
showing circuit lower bounds for NEXP.
Wed, 19 Jun 2002 18:00:01 +0300https://eccc.weizmann.ac.il/report/2002/038