Complexity invariance of real interpretations

The original publication is available at www.springerlink.comInternational audienceIn the field of implicit computational complexity, we are con- sidering in this paper the fruitful branch of interpretation methods. In this area, the synthesis problem is solved by Tarski's decision procedure, and consequently interpretations are usually chosen over the reals rather than over the integers. Doing so, one cannot use anymore the (good) properties of the natural (well-) ordering of N employed to bound the complexity of programs. We show that, actually, polynomials over the reals benefit from some properties that allow their safe use for complex- ity. We illustrate this by two characterizations, one of PTIME and one of PSPACE