Advisor: Dr. Chris Pollett

Description:

In recent years there has been an active research area which tries to give functional characterizations of time-bounded or space bounded complexity classes. An old example of this would be Cobham's [C64] characterization of PTIME using simple base functions on the natural numbers and closure under composition and bounded recursion on notation. Unfortunately, this characterization is restricted to natural numbers and thus makes it somewhat awkward to implement ``naturally'' occurring algorithms over other structures such as trees. Another avenue of research in this area, has been to give characterizations of these complexity classes which do not explicitly mention the resource bound in question. So for example, one would try to give a functional characterization of polynomial time that does not explicitly mention polynomials anywhere. Such characterizations have been given by Bellantoni-Cook [BC92] and Leivant [L93] under the names of safe recursion and tiered recursion. Still, both safe recursion and tiered recursion have disadvantages in that many naturally occurring polynomial time algorithms do not fit into the rather rigid discipline they impose. Recently, Hofmann [H02] gives a characterization of EXPTIME which allows computations over a variety of data structures such as lists or trees besides natural number. It also does not explictly mention resource bounds. Thus, if a programming language were developed out of this characterization it would give the user the illusion of being able to write code of arbitrary time complexity. Hofmann indicates that replacing general recursion with structural recursion reduces the strength of his system to polynomial time. My Master's goal is to come up with a subset/variant of C++ guaranteed to be polynomial time.

The reason why we are choosing a variant of C++ is that it is a language familiar to many programmers, so the learning curve would be quicker than for an arbitrary functional language. The idea would be to add a keyword to C++ called ``polynomial'' which one could tag functions or member functions with. the idea is such member function promise to run in polynomial time in their input parameters. We would write a translator from our ``feasible C++'' to regular C++ that translates code not contained in such a polynomial block verbatim into our target. For code in a polynomial block, the code will be parsed to make sure it satisfies the constraints of feasible C++ and, if so, the code will be converted to usual C++. The point of this is that if the translator successfully translate such functions without errors, it would then have verified that the algorithm is in fact a polynomial in its input parameters. The hope is that having such a verifier would help programmers to catch errors in implementing many common data structure algorithms.

Schedule:

Deliverables:

The full project will be done when CS298 is completed. The following will be done by the end of CS297:

1. The point of the first deliverable is to just get practical experience with some of the concepts from theory. Write a C program which simulates a Turing Machine program which starts with two numbers a,b separated by a dollar sign (user can supply these number from the command line) on its input and outputs their product.

2. Use Lex and Yacc to make a C program which can parse the ShML language of Professor Pollett's Fall '01 CS146 classes HW 2 and output the appropriate shape using character graphics. The point of this is to get familiar with lex and yacc.

3. Identify ``feasible'' functions/member functions for C++. Try to use notion of safe versus unsafe variables to do this, so do not have to mention resource bounds. Work with Professor Pollett to show correctness of this subset.

4. Write a translator that recognizes the polynomial keyword as suggested above and works correctly for the proposed restricted form of for loops.

5. CS 297 Report.

References:

[BC92] Stephen Bellantoni and Stephen Cook. New recursion-theoretic characterization of the polytime functions. Computational Complexity, 2:97-110, 1992.

[C99] P.Clote. Computation models and function algebras , Handbook of Computability Theory, ed. E.R. Griffor, Elsevier Science B.V. (1999). pp. 589--681.

[C64] Cobham, A. The intrinsic computational difficulty of functions. PROC. 1964 INTERNAT. CONGR. FOR LOGIC, METH., AND PHILO. OF SCI., North-Holland, Amsterdam, pp. 24--30.

[H02] Martin Hofmann. The strength of non-size increasing computation. Principles of Programming Languages. p. 260--269. ACM press. 2002.

[L93] Daniel Leivant. Stratified Functional Programs and Computational Complexity. In Proc. 20th IEEE Symp. on Principles of Programming Languages, 1993.

[LMB92] lex & yacc. Levine, Mason, and Brown. O'Reilly & Associates, Inc. 1992.

[Pap94] Computational Complexity. C.Papapdimitriou. Addison Wesley. 1994.