Deterministic Simulation in LOGSPACE

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n ) 2 / log log n passes the test with probability at least 1/ n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size. The sequence that we construct does not really depend on the test, in the sense that a polynomial family of sequences is constructed so that at least one of them passes any test. This family is the same even if the test is allowed to use an oracle of polynomial size, and it can be constructed in LOGSPACE (without using an oracle).

Authors

• Miklós Ajtai
• János Komlós
• Endre Szemerédi

Keywords

No keywords are indexed for this paper.