26 1. Classical Computation
b) Divide two integers with remainder: (a, b)
(
a/b , (a mod b)
)
,
where 0 a
2kb
and 0 b
2n.
In this case, construct a circuit of size
O(nk +
k2
log k) and depth O(log n + (log
k)2).
[2!] 2.15. Majority. The majority function MAJ :
Bn
B equals 1 for
strings in which the number of 1s is greater than the number of 0s, and
equals 0 elsewhere. Construct a circuit of size O(n) and depth O(log n) that
computes the majority function.
[3!] 2.16. Connecting path. Construct a circuit of size
O(n3
log n) and
depth O((log
n)2)
that checks whether two fixed vertices of an undirected
graph are connected by a path. The graph has n vertices, labeled 1,...,n;
there are m = n(n−1)/2 input variables xij (where i j) indicating whether
there is an edge between i and j.
2.3.3. Space and width. In the solution to the above problems we strove
to provide parallel algorithms, which were described by circuits of poly-
logarithmic depth. We now show that, if the circuit size is not taken into
account, then uniform computation with poly-logarithmic
depth3
is equiva-
lent to computation with poly-logarithmic space.
We are going to study computation with very limited space so small
that the input string would not fit into it. So, let us assume that the input
string x = x0 · · · xn−1 is stored in a supplementary read-only memory, and
the Turing machine can access bits of x by their numbers. We may think
of the input string as a function X : j xj computed by some external
agent, called “oracle”. The length of an “oracle query” j is included into
the machine work space, but the length of x is not. This way we can access
all input bits with space O(log n) (but no smaller).
Definition 2.2. Let X :
A∗

A∗
be a partial function. A Turing machine
with oracle X is an ordinary TM with a supplementary tape, in which it can
write a string z and have the value of X(z) available for inspection at the
next computation step.
In our case X(z) = xj, where z is the binary representation of j
(0 j n 1) by log2 n digits; otherwise X(z) is undefined.
The computation of a function f :
Bn

Bm
by such a machine is defined
as follows. Let x (|x| = n) be the input. We write n and another number
k (0 k m) on the machine tape and run the machine. We allow it to
query bits of x. When the computation is complete, the first cell of the tape
must contain the k-th bit of f(x). Note that if the work space is limited
by s, then n
2s
and m
2s.
The computation time is also bounded:
3As is usual, we consider circuits over a finite complete basis; the fan-in and fan-out are
bounded.
Previous Page Next Page