101

数理解析研究所講究録
第 666 巻 1988 年 101-104

A Rich Hierarchy on the Time Complexityof Uniform PRAMs

Kazuo Iwama

1. Introduction.
Motivation of introducing the unbounded fan-in circuit model is not unique: In[1] the authors found a connection between the complexity theory over this model anda famous open question (at that time) on the polynomial hierarchy. [4] proves that themodel can simulate the parallel random access machines with simultaneous writes(CRCW-PRAMs) of almost the same depth and size. Recently the present author
claims in [2] that the model can be much more useful than the bounded fan-in model
to study the depth hierarchy of Boolean functions. To this goal, however, it turns outthat the essential nonuniformity circuit models generally possess is a major obstacle
and that the best possible model we have currently seems to be (uniforn) CRCWPRAMs. The main result of [2] is the following.
be its inverse function
Let $A(i,j)$ be the Ackermann function and let$\overline{A}_{k}(n)=leastj$$A(k,j)\geqn$
such that. CRCW-PRAMs here denote parallel
defined byRAMs with simultaneous writes and with operations , –and 1 (bitwise OR). It
should be noted again that CRCW-PRAMs in this paper are unifom, namely, each
RAM has the same program not depending on the size of inputs. Then it follows:, there is a nondegenerate Boolean function
Theorem 1. For any constantby CRCW-PRAMs
steps to computeof variables such that it takeswith polynomial number of processors.
In this paper we extend this result, which suggests the existence of a rich hierarchy on the time complexity of Boolean functions. We will also show a result on arelation between the star-ffee regular expressions and the unbounded fan-in circuits
which might help removing the obstacle above mentioned (the nonuniformity of thecircuit models).
$\overline{A}_{k}(n)$$+$$c\geq 4$$G_{c}$$\Theta(\overline{A_{c}}(n))$$n$$G_{c}$

2. Time Hierarchy.
It should be noted that Theorem 1 is still true if $A_{c}(n)$ is replaced by its composi,,,(e.g.,
for constants
tion like. In this section we demonstrate that the hierarchy is$M$ be a Turing machine computing an integer function $f(n)$ byLetdense.
moremuchon its output tape from 1n on its input tape. Then $f$ is called aproducing$\overline{A_{c_{1}}}(\overline{A}_{c_{2}}(.

(\overline{A_{c_{i}}}(n)).

))$$c_{1}$$\overline{A}_{4}(\overline{A}_{4}(\overline{A}_{4}(n)))=\log^{*}\log^{*}\log^{*}n)$$1^{f(n)}$-1-$c_{2}$$\geq 4$$c_{j}$

102

polynomial-time function if $M$ halts within $T(n)$ steps for some polynomial . For
simplicity, we assume that $f$ is monotone, i.e., $f(n+1)\geq f(n)$ for all .
is replaced by any polynomial-time
Theorem 2. Theorem 1 is also true iffunction $f$ .
Proof. A straightforward modification of the proof of Theorem 1 [2]. Use asequence of configurations of the Turing machine that computes the polynomial-timefunction $f$ instead of the sequence of binary numbers. Details are omitted.
Corollary 1. Theorem 1 is still true for.
Proof. We will show that Ackermann function $A(i,j)$ can be computed in apolynomial number of steps on its answer (not on its input). Then it immediately follows that $A_{n}(n)$ is a polynomial-time function.
By definition $A(i,j)$ can be obtained by applying the following operations as far
as possible:
$T$

$n$

$\overline{A_{c}}(n)$$\square$$\overline{A}_{n}(n)$$A(0, y)=y+1$(1)$A(x+1,0)=A(x, 1)$(2)$A(x+1, y+1)=A(x, A(x+1, y))$(3)Thus, during the computation we always handle the form like$A(a_{0},$$A(a_{1}, \cdots A(a_{n-3}, A(a_{n-2}, a_{n-1}))\cdots)$,

which we denote by string$\sigma=a_{0}a_{1}\cdots a_{n-1}$.

be the sum of the integers
be the length of $\sigma(=n)$ and. Then one can see that:(i) $L(0)+S(0)$ does not change before and after applying operation (1) or (2).
(ii) Applying operation (3) increases $L(0)+S(0)$ by . Namely if $x=0$ thendoes not change either.
Since the final answer clearly does not exceed $L(0)+S(0)$, the number of times
operation (3) for positive (that makes $L(0)+S(\sigma)$ larger at least one) is applied mustbe less than the value of the answer. Therefore the total number of necessary applications of operations (1) $-(3)$ depends on the number of applications of those that do not
or operations (1), (2) and (3) for $x=0$ . It should be observed thatchangethe application of the operations is deterministic, i.e., the next operation is determineduniquely by the current . For example, when $0=a_{0}\cdots a_{n-2}a_{n-1}$ , operation (3) isandare positive. Now one can see that a lot ofapplied if and only if bothconsecutive applications of operations (1), (2) and (3) for $x=0$ occur when looks likeLet$L(\sigma)$$S(\sigma)$$(=a_{0}+\cdots+a_{n-1})$$x$$L(\sigma)+S(\sigma)$$x$$L(\sigma)+S(\sigma)$$\sigma$$a_{n-2}$$a_{n-1}$$\sigma$$o=\sigma_{1}a11\cdots 1b$( $m$ l’s, $a\geq 2$ andFor of this form, operation (3) has to be applied
then operation (1) $b+1$ times, which leaves$\sigma$$\sigma=\sigma_{1}a11\cdots 1(b+1)$-2-$b$$b\geq 1$).

times, operation (2) once and($m-1$ l’s).

103This sequence of operations is repeated until we run out all the l’s. Thus those operations that do not change $L(\sigma)+S(\sigma)$ can only continue $O(y\cdot m)$ times. Since bothandare less than the final answer, the total number of the whole operations do not
exceed the cube of the answer.
, we compute $A(i,i)$ for $i=1,2,$ .
To getsuccessively until the value
exceeds the input . On the tape, eachon the string may be represented by abinary number or a unary number. Clearly it does not take so many steps to carry out
the operations (1) $-(3)$ . Also it should be noted that if
becomes larger than foris $i-1$ .
the first time when computing $A(i,i)$ thenCorollary 2. There do not exist nonconstant lower bounds for the computation
time of CRCW-PRAMs.
Proof. It is enough to show that for any recursive function $g(n)$ there exists a
polynomial-time function $f(n)$ such that:(i)and$y$$m$$\overline{A}_{n}(n)$$\cdot$$n$$\sigma$$a_{i}$$L(\sigma)$$\overline{A}_{n}(n)$$n$$\square$$f(n) \leq\max_{\leq 0i\leq n}g(i)$(ii) $f(n)$ is not bounded by any constant if

is not.
Let $M$ be a Turing machine which computes $g(n)$ . We construct the Turing machine
computes $f(1),$ $f(2)$ and sothat computes $f(n)$ as follows: By simulating $M,$
$N$ of its moving
successively
thesametime
itcountsthenumberand aton
steps (one$N$$M’s$
one step). Suppose that when becomes (the input
step for the simulation ofhalts with leaving on its output tape the maxto )is computing $f(i)$ . Then, and $f(i-1)$ . It is not hard to see this $f(n)$ meets theimum value in $f(1),$ $f(2)$ ,above conditions (i) and (ii).
$g$

$T$

$T$

$n$

$T$

$T$

$T$

$\square$

3. Star-Free Regular Expression vs. Unbounded Fan-In Circuits.
In this section we show a sufficient condition analogous to the Unger’s wellover {0,1} is a regular set then can beknown one [5] that says if a languagerecognized by bounded fan-in circuits of depth $O(\log n)$ and size $O(n)$ . Our present
one is:be a homomorphism ffom into 0,1
Theorem 3. Let be an alphabet,and be a star-ffee regular expression over . Then if the on-set of a Boolean function can be given by $h(L(R))$ ($L(R)$ is the language generated by ), is comof a constant depth and a polynomial size on
puted by an unbounded fan-in circuit
$s$

$L$

$L$

$h$

$\Sigma$$R$$\Sigma$$\{$$\}^{*}$$\Sigma$$R$$f$$f$$C$$n$.

is a regular
By definition, a star-free regular expression over alphabet
for each in and, as operations, complement, union
expression that can use
Theorem 3 could help to introduce a desirable, intersection $\cap and$ concatenation
unifornity to the unbounded fan-in circuits. (The common uniformity for the bounded
fan-in circuits [3] can of course be applied to the unbounded fan-in model but it is too
weak to discuss relatively low depth complexity. See [2].)and suppose that the regular
Proof of Theorem 3. Let.
, $R_{k}=R$ . Then we constructexpression
consists of subexpressions,,
whereforeachandsuch that
expressions
Boolean,,,of the target Boolean expression (oris the number of variables$\Sigma$$\phi,$$\epsilon,$$0$$\sigma$$\Sigma$$\cup$$\Sigma=\{a_{1}, a_{2}, \cdot.

$R$

$k$

$f_{i^{1}j},$, a_{m}\}$$R_{1},$ $R_{2},$$f_{i^{2}j}$$i$$f_{i}^{k_{j}}$$x_{1},$$x_{2}$$x_{n}$-3-$\cdot$$j$$0\leq i\leq j\leq n$$n$104

equivalently the circuit
the following form:(i). Then(ii). Then$C$).

$f$

for all andfor all and$f_{i^{l},j}=0$$R_{l}=\phi$$f_{i^{l},i}=1$$R_{l}=\epsilon$

is obtained as$f=f_{0,n}^{k}$. Now the expressions

.

$i$

$j$

$i$

$f_{i,j}^{l}=0$

for alland

$i$

$j$

such that$i\neq j$$f_{i^{l},j}$are of.

(iii) $R_{l}=a_{t}(\in\Sigma)$ .
$f_{i^{l},j}=0$$\overline{x_{i+s}}$

Suppose that $h(a_{t})=c_{1}c_{2}\cdots c_{p}(c_{1}, \cdot\cdot , c_{p}\in\{0,1\})$ . Then
ifandif $j\neq i+p$ . Otherwise $f=x’x’\cdots x_{i+p}’$ whereis$x_{i+s}’$$x_{i+s}$$c_{s}=1$

if $c_{s}=0$ .
(iv) $R_{l}=R_{p}\cup R_{q}$ . Then(v) $R_{l}=R_{p}\cap R_{q}$
(vi)
(vii)

$R_{l}=\overline{R_{p}.}$. Then

Then. Then$f_{i\underline,j^{=}}^{l}(f_{\iota}^{p_{j}},f_{\iota,j}^{g})$$f_{i^{l},j}=(r_{\iota}^{p_{j}},)$$R_{l}=R_{p}\cdot R_{q}$for all and .
for $dli$ and .
$i$$f_{i^{l},j}=(f_{\iota}^{p_{j}},+f_{\iota}^{g_{j}},)$

$j$

$j$

for $aUi$ and .
for all and
$j$

$i$

$f_{i^{l},j}=( \sum_{i\leq s\leq j}f_{\iota}^{p_{s}},f_{s^{q},j})$$j$.

To show the correctness of the construction, we prove the validity of the following sentence by the mathematical induction on the number of operations involved inthe expression :$R$$f_{i^{l},j}(x_{1}, x_{2}, \cdot.

, x_{n})=1$

if and only if $v_{i+1}v_{i+2}\cdots v_{j}\in h(L(R))$. Details may be omitted since it iswhereis the value ( or 1) of the variablea standard application of the induction method.
As for the number of (unbounded fan-in) gates to realize the expression $f$ , thefollowing observation will be enough: (a) The number of Boolean expressions
is$O(n^{2})$. (Note that the length of or the number of its subexpressions is a constant.)(b) To realize
by circuit, we need only $O(1)$ gates for all the construction rules$(i)-(vi)$ . (c) For the rule (vii) also, one can see that $O(n)$ gates are enough. Thus thetotal number of gates neCeSSary for the above ConStruction is $O(n^{3})$ . 口$0$$v_{i+s}$$x_{i+s}$$f_{i^{l},j}$

$R$

$k$

$f_{i^{l},j}$References

1.

M. Furst, J. Saxe, and M. Sipser, ‘Parity, circuits and the polynomial-time hierarchy,” Proc. 22nd IEEE Symp. on Foundations of Computer Science, pp. 260-270,‘1981.

2.
3.
4.
5.

K. Iwama, “Very small tight bounds on the time of uniform PRAMs with simultaneous writes,” Tech. Rep. COMP87-64, Institute of Elec. Inform. Comm. Eng.
of Japan, 1987.
W. L. Ruzzo, “On uniform circuit complexity,” J. Comput. Syst. Sci., vol. 22,
pp. 365-383, 1981.
L. Stockmeyer and U. Vishkin, ‘Simulation of Parallel Random Access Machines
by Circuits,” SIAM J. Comput., vol. 13, pp. 409-422, 1984.
S. H. Unger, “Tree Realization of Iterative Circuits,” IEEE Trans. Comput., vol.
C-26, pp. 365-383, 1977.
‘-4-