Determinism versus non-determinism for linear time RAMs (extended abstract)
Miklós Ajtai · 1999
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 wile memory.We measure the time by the number of accesses to the input registers.We show thal 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 wile memory.that is.there is no machine with this values of the parameters which decides whether there are two different input registers whose contents are identical.Intmduction.One of the main goals of complexity theory is the separation of non-deterministic and deterministic computation.We solve the problem for random access machines with certain restrictions on the size of their working memory.Although the restrictions are strong, the working memory must be smaller than the input.still.under certain circumstances this computational model is realistic as we will explain later.Our seacrh problem.as described in the abstract is the element distinctness problem.that is.we have to decide whether there are different input registers with identical contents.We also show that there is a simple decision problem that can be solved in constant time (actually in IWO steps) using non-deterministic computation, while there is no deterministic linear time algorithm with enlogn bits read and write memory which solves the problem.More precisely if we allow kn time for some fixed constant k, then there is an 6 > 0 so that the problem cannot be solved with in log n bits of read and write memory if n is sufficiently large.The decision problem is the following: "Find two different input registers, so that the Hamming distance of their contents is at most i c log n".i can be replaced by any fixed 0 < 7 < 4 if c is sufficiently loge with respect to 7. We actually show that the promise problem : "decide whether all occurring Hamming dist'ances are greater than ($ -r)c log n