|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
Time and Space Complexity of Reversible Pebbling
by Richard Kralovic
Abstract:
In connection with quantum computing, reversible computations are very
important. In this paper the model of the reversible pebble game is introduced.
Reversible pebble game is an abstraction of a reversible computation, that
allows to examine the space and time complexity for various classes of problems.
We will show a technique for proving lower and upper bounds of time and space
complexity. Using this technique we will show a tight space bound ($\Theta(\lg
n)$), upper and lower bounds on time for optimal space ($O(n^{\lg 3})$,
$\Omega(n\lg n)$) and an upper bound on time-space tradeoff for a chain topology
(space $O(\sqrt[k]{n})$ for time $2^k n$). Further, we will show a tight
optimal space bound for a binary tree topology ($\Theta(n+\lg^* n)$) and we
will discuss space complexity for a butterfly topology. By these results we
show, that for reversible computations more resources are needed in
comparison to standard computations.