THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH IABORATORY1 Algebras of Feasible FuncLions Yuri Gurevich CR1.-TR-21 -83 MAY 1983 Computing Research laboratory Room 1079. East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 1All correspondence should be senl. to P-'roressor Yuri Gure:vicl. Any opinions, findings, and conclusions or recommendations expressed in this publickatiorn are those of the authors and do not necessarily reflect the views of the funding agencies.

- 1 - Algebras of feasible functions Yuri Gurevich, University of Michigan Introduction. For different complexity levels (PTIME, LOGSPACE, etc.) and an arbitrary set a of functions we give an inductive definition of the class of functions computable from a within the complexity level. Our inductive definition for the class of PTIME computable functions is different from and more robust than the inductive definition of Cobham [Co] for the same class. As far as we know, it is the first time that inductive definitions for the other complexity classes have been given. The idea is to view computable functions as database queries rather than pure arithmetical objects. For example, the function fG(x):=the diameter of the connected component of vertex x of graph G can be coded into a pure arithmetical function. We prefer, however, to view it as a kind of global function (or a function schema) that becomes an ordinary function in each graph. Global functions are defined precisely in ~1. The usual definition of primitive recursive functions, adapted to global functions, surprisingly gives exactly LOGSPACE computable global functions, see ~2. Recursive global functions appear to be exactly PTIME computable global functions, see ~3. To show that our approach can handle some other complexity classes, we mention some more results in ~4. This work is related in spirit to [Im2], and its subject could be called functional (rather than predicate) logic. One advantage of our approach is that computations in context can be expressed in our logic in a way that preserves bounds on the resources in question.

-2~1. Global predicates and functions Consider the statement "Vertices x and y of the graph are connected", For each graph this statement becomes a binary predicate. We call such a statement a global predicate (or predicate schema). Analogously, a term (xy)z gives a ternary function for each set with a binary operation on it. It is an example of a global function (or function schema). From this point of view first-order or second-order formulas are global predicates. A relational query is a global predicate or a global function. We will define global predicates and functions formally. A vocabulary a is here a finite list of predicate and function symbols with specifications of the arity of each predicate symbol and the arity and the co-arity of each function symbol. A structure S of a vocabulary a is a nonempty set U (the universe) together with interpretations of all symbols in a. An Z-ary s U predicate symbol P is interpreted as a predicate PSc U. A function symbol f S ak- r -arity of arity a and co-arity r is interpreted as a function f:U U. (The co-arity r is always positive.) If ==O,r=l then the function symbol is interpreted as an individual constant. The same name is used often for a structure and its universe. The cardinality ISI of a structure S is the cardinality of its universe. Here is a typical example: a consists of one binary predicate symbol, a-structures are (directed) graphs. We will view structures as inputs for algorithms. Proviso 1. The term "structure" will refer to structures S of finite cardinality with Universe (S)={O,1,...,SI-1l}. A global i-ary predicate P of vocabulary a (in short, an 9-ary a-predicate P) assigns to each a-structure S an ordinary k-ary predicate PScS. A global function f of vocabulary a (in short, a a-function f) of arity a and co-arity r assigns to each o-structure S a function fS:S +Sr. (The superscript S will usually be omitted.)

- 3Symbols of a vocabulary a name so-called basic a-predicates and a-functions. The difference between the basic and the other a-predicates and a-functions is intentional. The first provide parts of inputs, the second provide objects to be computed. Pseudo-Claim. Let a be a vocabulary, z be a natural number and E be an S k alphabet. Let f assign to each a-structure S a function f:S -z. Then f is a global function. Instead of relaxing the definition of global functions we choose (at this stage) the following way to make the Pseudo-Claim true. First, we disregard structures of cardinality 1. Proviso 2. Only structures of cardinality at least 2 are considered. Second, we code the letters of z by tuples of zeroes and ones of the same length r. The given f becomes a a-function of arity z and co-arity r. We use the term "vector" for tuples of elements (of a structure). With each vector x=(xl,...,xm) of elements of a structure S we associate a number, S-value(x):=xilSIm1i. To compute the S-value of x just view the vector x as an ISI-adic number. The Pseudo-Claim allows us to see a function g:z-*+z with Ig(u)1<_ulm for some m, as a global function. Namely, let's disregard the words in z* of length <1. Then a word wez* can be seen as a structure of cardinality IwI with a unary basic function taking values in zO. Pad g(w) to a word gl(w) of length Jwlm using a new symbol (the blank). Define gW(x1,...,xm) to be the kth letter of the gl(w) where k is the w-value of (x,...,xm). We will say that a computational device computes an Z-ary a-function f if, given a a-structure S and a vector xcS, the device computes fS(x). The size of the input (S,x) is supposed to be at least ISI.

-4~2. LOGSPACE computable functions We adapt the usual definition of primitive recursive functions to the case of global functions and show that for each vocabulary a, LOGSPACE computable a-functions are exactly primitive recursive a-functions. First, we describe initial primitive recursive functions of the empty vocabulary. Individual constants 0 and End, and constant functions Zero(x)=O, END(x)=End. The individual constant End is interpreted as |S|-1 in each structure S. Thus, the function END is constant on each structure S but its value depends on IS{. Successor functions mSc(xl,... xm) for m>l. If S is a structure, xESm and S-value(x)<JlSm-l then mSc(x) is the vector yeSm with S-value(y)=S-value(x)+l. In this case we will usually write x+l instead of mSc(x). If, on the other hand, x-Endm then mSc(x)=O. Projection functions mP(x,...,xm)=(x,...,x ) where l<il<i2<...<i<m 5- ms i 1' i i\X and s is the sequence il,...,i. Second, for every nonempty vocabulary a the basic functions fea and the characteristic functions of the basic predicates Pea are initial primitive recursive o-functions. Third, we describe two operations on global functions. Composition f(x):=g(hl(x),...,hm(x)). The notation is not perfect here. The values hl(X),...,hm(x) should be concatenated into one vector because the domain of every fS consists of vectors rather than tuples of vectors. Primitive recursion: f(x,O):=g(x), (1) \ f(x,t+l):=h(x,t, f (x,t)). Here t+l is the successor of t and t+lfO. A global function of some vocabulary o will be called primitive recursive (shortly PR) if it belongs to the closure of the initial primitive recursive functions of vocabulary o under composition and primitive recursion.

-5Theorem 1. Let o be an arbitrary vocabulary. A global o-function is LOGSPACE computable iff it is primitive recursive. The if direction is easy. The only if direction is proved in the rest of the section. We begin with a few easy lemmas. Lemma 1. Let f(x,y) be a global function of some vocabulary a1 and let o2 be the extension of ao by a new individual constant c. If the a2-function g(x):=f(x,c) is PR then f is a PR ol-function. A global a-predicate will be called PR if its characteristic function is so. Lemma 2. (i) Any boolean combination of PR a-predicate. (ii) Suppose that a a-function f is defined by cases f(x)= (x) if P1(x) f(x):= g9m(X) if Pm(X) If the o-functions 91g,.'g m and the a-predicates Pl,..,Pm are PR then f is so. Lemma 3. Suppose that a global o-function f is a concatenation of global a-functions fl"...fm: f(x):=(fl(Xl),... fm(Xm)) where each x. is a projection of x. If fl'**fn are PR then f is so, and vice versa. Lemma 4. Suppose that o-functions fl,f2 are defined by a simultaneous primitive recursion: f (x'O):=g (x)' fi (x,t+1):=h i (x,t, fl (xt)' f 2 (x't)) If the global o-functions gi,hi are PR then fl'f2 are so. Now, let f be a LOGSPACE computable o-function. We will show that f is PR. Due to Lemmas 1 and 3 we can suppose that the arity of f is zero and the co-arity of f is one.

- 6 - Since f is LOGSPACE computable there is a two-way multihead finite automaton M that computes f. We can suppose the following about inputs S. Each basic predicate pS is presented on a separate input tape of length IS|' where k is the arity of P. The cells of the tape are numbered by (the S-values of) vectors of dimension Z. A cell x codes the truth-value of P(x). The components fS.fr of a basic function fS of co-arity r are presented on separate input tapes as their respective graph predicates. The components of the output vector are printed in the unary notation on separate output tapes. Let H1,..,H be the heads of M. Let Symi(xi) be the content of cell x. of the tape for Hi. The functions Sym. are easily definable by cases. For example, if Hi works on the input tape for some basic predicate P then there are 6 cases determined by the truth-value of P(xi) and by whether cell x is leftmost, rightmost or neither. Hence the functions Symi are PR. Hence the concatenation Sym(x) of Sym (x),...,Symm(x) is PR. The steps of the computation of f can be numbered by vectors t of some dimension k. Let State(t) be the state of M at moment t. Let Headi(E) be the position (cell) of Hi at moment t, and let Head(t) be the concatenation of Headl(t),...,Head m(). It is easy to define by cases PR functions a,B such that State(t+l)=a[State(t), Sym(Head(t))], Head(t+l )=[State(t), Head(t)]. The zero-ary functions State(Ok), Head(Ok) are obviously PR. By Lemma 4, State and Head are PR. Let Print(t) express that M prints on the output tape at moment t, This o-predicate is easily definable by cases and therefore is PR. Finally, we define a PR a-function Out(Ok)'O, Out(Ok):O_ Out(t)+l if Print(t), Out(t+l):=' ( Out(t) otherwise, and note that f(t)=Out(Endk).o

~3. PTIME computable functions We justify the thesis that for each vocabulary a, PTIME computable a-functions are exactly recursive o-functions. Fix a. PTIME computable o-functions are closed under many kinds of recursion. For example, let (f(x,0):=9g(x-), (2) { (f(x,t+l) h(xt,f(Yl,t),.,f(Ym,t)) where y- j:=ai(f(xT)). If the a-functions g,h and ai are PTIME computable then f is so: for each t compute f(x,t) for all x. Recall that x takes only polynomially many values. Moreover, suppose that a o-function f is defined by some recursion from PTIME computable o-functions. The arguments of f take only polynomially many values. It is natural to suppose that the recursive definition gives a computation where each round provides a new value of f in a polynomial number of steps. Hence all values of f can be computed in a polynomial number of steps. In this sense PTIME computable functions are closed under any recursion. (The phenomenon is related to the fact that a-predicates are closed under the least fixed point operator.) In order to define recursive a-functions formally we are looking for a particular recursion schema. An essential difference between recursions (1) and (2) is that the parameters are not altered in (1). A disadvantage of recursion (2) is that for each t+l we have to update values f(x,t) for each x. If (2) reflects some computation with t coding the steps and if we use (2) to compute f then we end up with a much worse time bound than that for the original computation. The following schema gives minimal updating. f(O):=g, F(x,O):=G(x), f(t+l);=h(f(t), F(f'(t),t)), (3) (F(x,t) if x~f(T), F(x,t+l);= F H(f(t), F(x,t)) otherwise. Here f'(t) is the projection of f(t) on the first Dimension(x) components.

- 8 - We will say that a global a-function is recursive if it belongs to the closure of the initial primitive recursive a-functions under composition, primitive recursion (1) and recursion (3). Theorem 2. A global a-function f is PTIME computable iff it is recursive. The proof is similar to that of Theorem 1. We sketch here only a part that is essentially new. Fix a Turing machine M that computes f. The time (computational steps) can be represented by k-tuple t of individual variables. Let HO,H,...,Hm be the heads of M where H0 works on the working tape and H1,...,Hm work on input tapes. For i=O,l,...,m let Headi(t) be the position of H. at time t, let State(t) be the state of M at time t, and let Head(t) be the concatenation of Heado(t), Headl(t),..., Headm(t), State(t). Let SymO(x,t) be the symbol in cell x of the working tape at time t. For i=l,...,m let Sym.(xi) be the symbol in cell xi of the input tape for Hi. As in the proof of Theorem 1 the functions Syml,...,Symm are PR. Now use the recursion schema (3) with f(t)=Head(t), f'(t)=Heado(t) and F(x,t)=Symo(x,t). The corresponding functions h and H are primitive recursive. They use Symi(Headi) for i=l,...,m and are easily definable by cases.

~4. A combined restriction on time and space k We say that a function is PTIME-LOG -SPACE if it can be computed on a Turing machine under a simultaneous restriction of polynomial time and logk space. We say that a function is PTIME-PLOGSPACE if it is PTIME-LOGk-SPACE for some k, This section gives inductive definitions of all these classes of functions. We generalize the notion of global functions by introducing a new sort of individual variables, called log-restricted variables. Log-restricted variables range over natural numbers less than or equal to log21SI in each structure S. Defining a global function f(xl,...,xZ)=(yl,...,yr) we have to specify now which variables xi,Yi are log-restricted. Fix a vocabulary a. PTIME-PLOGSPACE computable a-functions are closed under a wide variety of recursions with log-restricted parameters. Consider, for example, the recursion schema (2) and suppose that the components of x are log-restricted. If a-functions g,h,ai are PTIME-PLOGSPACE computable then f is so. Theorem 3. A global o-function f is PTIME-PLOGSPACE iff it can be obtained from initial primitive recursive a-functions by composition, primitive recursion and recursion (3) where all parameters are log-restricted. Theorem 4. A a-function f is PTIME-LOGk-SPACE iff it can be obtained from initial primitive recursive o-functions by composition, primitive recursion and recursion (3) where Dimension(x)<k and all components of x are log-restricted. We could avoid introducing a new sort of individual variables because the following global function is primitive recursive: the length of the binary notation for x+l.

- 10 - Concluding remarks. This paper is a continuation of [Gu] where we argue for altering classical logic in order to make it more appropriate to Computer Science. We believe that algebras of feasible functions may be useful for creating new query languages, for creating special purpose programming languages and for proving (or disproving) properties by induction. We do not believe that deep problems such as P=?NP can be solved simply by translating them into algebra or logic. However, such translations can shed some new light on these problems, Acknowledgements. Papers [Iml], [Va] and discussions with Neil Immerman were useful in my work on the preceeding paper [Gu]. This paper has gained from useful comments of my Michigan colleagues Andreas Blass, Peter Hinman, Jane Kister and Bill Rounds. References [Co] A. Cobham, The intrinsic computational difficulty of functions, Proc. 1964 Internat. Congress for Logic, Method. and Phil. of Sciences, NorthHolland. [Gu] Y. Gurevich, Logic tailored for computational complexity, to appear. [Iml] N. Immerman, Relational queries computable in polynomial time, 14th ACM Sympos. on Theory of Computing, San Francisco, May 1982, 147-152. [Im2] N. Immerman, Languages which capture complexity classes, 15th ACM Sympos. on Theory of Computing, Boston, April 1983, 347-354. [Va] M. Vardi, Complexity of relational query languages, 14th ACM Sympos. on Theory of Computing, San-Francisco, May 1982, 137-146.