Browse Prior Art Database

Algebras of Feasible Functions

IP.com Disclosure Number: IPCOM000128454D
Original Publication Date: 1983-May-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 98K

Publishing Venue

Software Patent Institute

Related People

Gurevich, Yuri: AUTHOR [+3]

Abstract

For different complexity levels (PTIME, LOGSPACE, etc.) and an arbitrary set sigma of functions we give an inductive definition of the class of functions computable from sigma 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 ( A. Cobham, The intrinsic computational difficulty of functions, Proc. 1964 Internat. Congress for Logic, Method. and Phil. of Sciences, North-Holland.) 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 f G (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 [ Section ] 1. The usual definition of primitive recursive functions, adapted to global functions, surprisingly gives exactly LOGSPACE computable global functions, see [ Section ] 2. Recursive global functions appear to be exactly PTIME computable global functions, see [ Section ] 3. To show that our approach can handle some other complexity classes, we mention some more results in [ Section ] 4. This work is related in spirit to ( N. Immerman, Languages which capture complexity classes, 15th ACM Sympos. on Theory of Computing, Boston, April 1983, 347-354.) , 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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Algebras of Feasible Functions

Yuri Gurevich

CRL-TR-21-83

MAY 1983

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 Computing Research Laboratory
Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

Introduction

For different complexity levels (PTIME, LOGSPACE, etc.) and an arbitrary set Σ of functions we give an inductive definition of the class of functions computable from Σ 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 Cobham2 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 [ Section ] 1. The usual definition of primitive recursive functions, adapted to global functions, surprisingly gives exactly LOGSPACE computable global functions, see [ Section ] 2. Recursive global functions appear to be exactly PTIME computable global functions, see [ Section ] 3. To show that our approach can handle some other complexity classes, we mention some more results in [ Section ] 4.

This work is related in spirit to3, 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.

[ Section ] 1. Global predicates and functions

1 All correspondence should be sent to Professor Yuri Gurevich. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

2 A. Cobham, The intrinsic computational difficulty of functions, Proc. 1964 Internat. Congress for Logic, Method. and Phil. of Sciences, North-Holland.

3 N. Immerman, Languages which capture complexity classes, 15th ACM Sympos. on Theory of Computing, Boston, April 1983, 347-354.

University of Michigan Computing Research Laboratory Page 1 May 01, 1983

Page 2 of 7

Algebras of Feasible 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...