Two time-space tradeoffs for element distinctness (Q1095660): Difference between revisions

Two time-space tradeoffs for element distinctness are given. The first one shows \(T^ 2S=\Omega (n^ 3)\) on a branching program using minimum operations. By a result of \textit{A. C. C. Yao} [ibid. 19, 203-218 (1982; Zbl 0547.68062)], this implies the same bounds for linear queries. The second result extends one by \textit{P. Dúriś} and \textit{Z. Galil} [Math. Syst. Theory 17, 3-12 (1984; Zbl 0533.68047)] who constructed a Boolean function that requires \(T^ 2S=\Omega (n^ 3)\) on a k-headed Turing machine. Here it is shown that their proof also holds for element distinctness, a more natural problem.