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.