Time-space trade-off lower bounds for randomized computation of decision problems

摘要: We prove the first time-space lower bound trade-offs for randomized computation of decision problems. The bounds hold even in case that is allowed to have arbitrary probability error on a small fraction inputs. Our techniques are extension those used by Ajtai and Beame, Jayram, Saks applied deterministic branching programs. results also give quantitative improvement over previous results.Previous trade-off problems can be divided naturally into functions with Boolean domain, is, each input variable {0,1}-valued, large where takes values from set whose size grows number variables.In exhibited an explicit class functions, proved any program or RAM using space S = o(n) requires superlinear time T compute them. functional form not given his paper, but optimizing parameters arguments gives Ω(n log n/log n) O(n1-ϵ). For same considered Ajtai, we (for programs error) √ log(n/S)/log (n/S)). In particular, O(n1-ϵ), this improves Ω(n√ n).In domain case, (n/S)) element distinctness function Ajtai's Hamming closeness problem certain associated quadratic forms fields.