✦ LIBER ✦
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions
✍ Scribed by Miklós Ajtai
- Book ID
- 102587345
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 317 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
Our computational model is a random access machine with n read only input registers each containing c log n bits of information and a read and write memory. We measure the time by the number of accesses to the input registers. We show that for all k there is an e > 0 so that if n is sufficiently large then the elements distinctness problem cannot be solved in time kn with en bits of read and write memory; that is, there is no machine with this value of the parameters which decides whether there are two different input registers whose contents are identical.