期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove the first time-space lower bound tradeoffs for randomized
computation of decision problems. The bounds hold even in the
case that the computation is allowed to have arbitrary probability
of error on a small fraction of inputs. Our techniques are an
extension of those used by Ajtai in his time-space tradeoffs for
deterministic RAM algorithms computing element distinctness and for
Boolean branching programs computing a natural quadratic form.
Ajtai's bounds were of the following form: if the machine uses at most
kn time for some constant k it requires space at least
kn for some constant k. In this paper we
provide an explicit relationship between k and k that
achieves larger lower bounds than those proven by Ajtai.
In particular, we obtain time-space tradeoff lower
bounds of the form T=(nlogloglog(nS)) , which
implies that if the space is n1− then
the time used is (nlogloglog(n)) .
