期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2005
卷号：2005
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：Miklos Ajtai in "Determinism versus Non-Determinism for Linear Time RAMs with
Memory Restrictions", 31st Symposium on Theory of Computation (STOC), 1999 has
proved that any R -way branching program deciding the so-called Hamming
distance problem (given n elements decide whether any two of them
have ``small'' Hamming distance): in time O(n) must use space Omega(n lg n).
