Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions
复制标题
具有内存限制的线性时间 RAM 的确定性与非确定性
DOI：
10.1006/jcss.2002.1821
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Ajtai
中科院分区：
文献类型：
--
作者：
M. Ajtai
我们的计算模型是一个随机存取机与n个只读输入寄存器，每个包含c日志n位的信息和一个读写存储器。我们通过访问输入寄存器的次数来测量时间。我们表明，对于所有的k有一个e > 0，因此，如果n是足够大的，那么元素的独特性问题不能解决的时间kn与en位的读写存储器，也就是说，没有机器的参数，决定是否有两个不同的输入寄存器的内容是相同的。
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.