26 1. Classical Computation
b) Divide two integers with remainder: (a, b) →
a/b , (a mod b)
where 0 ≤ a
and 0 b
In this case, construct a circuit of size
log k) and depth O(log n + (log
[2!] 2.15. Majority. The majority function MAJ :
→ 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
log n) and
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
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 :
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 :
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 ≤
and m ≤
The computation time is also bounded:
3As is usual, we consider circuits over a finite complete basis; the fan-in and fan-out are