Computing with arbitrary and random numbers

We consider integer random access machines (RAMs) that receive one of two types of special integers as extra inputs: arbitrary numbers and random numbers. Arbitrary numbers are numbers that have no special property, other than being large-valued. Informally, one can consider them as adversarially-chosen numbers. Intuitively, it would not seem that arbitrary numbers offer any value. However, previous studies have shown for specific problems that such numbers contribute to the computational power of a RAM. The present work gives, for the first time, a broad characterisation of the scenarios in which arbitrary numbers do and those in which they do not increase computational power, rather than considering specific problems. The second type of extra inputs, random numbers, is conceptually an intermediate ground between Oracle-given certificates and adversarially-chosen arbitrary numbers. The contribution of random inputs to Turing machines is the famous P=RP problem. In the context of RAMs, it was posed as an open question by Simon (1981). The present study closes this problem, by showing that for certain RAMs randomness does provide an advantage, whereas for others it does not. In order to achieve the results presented, this work also reviews classical results regarding certificates and the use of indirect addressing (which is a pseudo-operation available to RAMs, but which can be conceptually disabled so as to have its contribution modelled). In both cases, our results sharpen the state-of-the-art. In the case of certificates, we show how results by Simon (1981) on RAMs with certificates continue to hold also with a slightly reduced operation set (as well as with new operation sets). In the case of indirect addressing, we show how, for specific RAMs, this pseudo-operation can be simulated with no loss of complexity, whereas previously the state of the art was for a loss of complexity by a factor of the inverse Ackermann function. The following are some of our main results. We define a new complexity class, PEL, which formalises the idea of describing the power of a RAM in terms of its capacity to generate large numbers, and show that for a wide class of RAMs (specifically those that support addition, Boolean operations, left-shift by a variable amount and division) computational power is, indeed, directly related to this capacity. In particular, the addition of an arbitrary large number to any RAM belonging to this class gives it the ability to recognise any recursively enumerable set in O(1) time. Indeed, functions computable in this model are on the second level of the arithmetical hierarchy. When adding to this the ability to generate additional arbitrary large numbers at will, we show that an O(1)-time computation has the same power as the entire arithmetical hierarchy, and an omega(1)-time computation extends even beyond that. For certain other RAMs, we are able to show that the addition of arbitrary large numbers does not increase their computational power at all. For RAMs that have access to random numbers, we close an open problem raised by Simon (1981), who asked for a characterisation of the power of certain RAMs working in polynomial time on random numbers. Intriguingly, the power of these RAMs is PEL, too. However, it remains an open question whether they, too, enjoy the power-boost afforded by arbitrary large numbers.Awards: Winner of the Mollie Holman Doctoral Medal for Excellence, Faculty of Information Technology, [2013]