On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines

W. Maass

Abstract:

We prove optimal lower bounds on the computation time for several well-known test problems on a quite realistic computational model: the random access machine. These lower bound arguments may be of special interest for logicians because they rely on finitary analogues of two important concepts from mathematical logic: inaccessible numbers and order indiscernibles

Reference: W. Maass. On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines. J. Symbolic Logic, 53:1098-1109, 1988.