Skip to Main content Skip to Navigation
Conference papers

Complexity invariance of real interpretations

Abstract : In 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Guillaume Bonfante Connect in order to contact the contributor
Submitted on : Friday, November 12, 2010 - 5:06:17 PM
Last modification on : Wednesday, June 1, 2022 - 4:40:38 AM
Long-term archiving on: : Friday, October 26, 2012 - 3:31:01 PM


Files produced by the author(s)



Guillaume Bonfante, Florian Deloup. Complexity invariance of real interpretations. 7th Annual Conference on Theory and Applications of Models of Computation - TAMC 2010, Jun 2010, Prague, Czech Republic. pp.139-150, ⟨10.1007/978-3-642-13562-0⟩. ⟨inria-00535784⟩



Record views


Files downloads