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

Publisher Website
Google Scholar
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.

This publication has 0 references indexed in Scilit: