Arnold Beckmann
Theoretical Computer Science Vol. 288 No. 1, pp. 3-19
Publication year: 2002

We define a coding of natural numbers — which we will call the exponential notations — and interpretations of the less-than-relation, the successor function, addition and exponentiation on the exponential notations. We prove that all these interpretations are polynomial time computable. As an application we show that we can interpret terms over a certain restricted language — including exponentiation — in polynomial time on exponential notations.

Leave a Reply

Your email address will not be published. Required fields are marked *