FOR RANDOM ACCESS MACHINES

Abstr¡ct. wc prove optimal lower bounds on the computation time for several well-known test problems on u quiå realistic computational model: the random access machine ' These lower bound arguments may be of special intefest for logicians because they rely on finitary analogues of two importai "on."pt, from mathematical logic: inaccessible numb€rs and ordcr indiscernibles. loP in this PaPer a new lower bound bounds on the computation time for realistic computational model: the mially many registers. These lower for logicians because theY relY on frnitary analogues of two concepts from mathematical logic: inaccessible numbers and order íniliscernibles. In particular we prove in $2 an optimal lower bound of O(n log n) for the problems ELEMENT DISTINCTNESS:: {(tr,...,xo) € N " lx ¡ # x,for i * i\ and DISJOINT SETS:: {(yr,. ",!n¡2,2r,"',zntz) e N " I n is even an