4702087_monash_120300.pdf (977.39 kB)

Download file# Computing with arbitrary and random numbers

thesis

posted on 28.02.2017, 04:59 by Brand, MichaelWe 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].