Complexity invariance of real interpretations

Guillaume Bonfante; Florian Deloup

inria-00535784, version 1

Complexity invariance of real interpretations

Guillaume Bonfante () ¹, Florian Deloup ()^a^, 2

7th Annual Conference on Theory and Applications of Models of Computation - TAMC 2010 6108 (2010) 139-150

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.

a – Université Paul Sabatier - Toulouse III
1: CARTE (INRIA Nancy - Grand Est / LORIA)
CNRS : UMR7503 – INRIA – Université de Lorraine
2: Institut de Mathématiques de Toulouse (IMT)
Université Paul Sabatier [UPS] - Toulouse III – Université Toulouse le Mirail - Toulouse II – Université des Sciences Sociales - Toulouse I – Institut National des Sciences Appliquées (INSA) - Toulouse – CNRS : UMR5219

inria-00535784, version 1
http://hal.inria.fr/inria-00535784
oai:hal.inria.fr:inria-00535784
From: Guillaume Bonfante <>
Submitted on: Friday, 12 November 2010 17:06:17
Updated on: Monday, 15 November 2010 10:28:48

See detailed view

Associated documents

PDF :

DOI: 10.1007/978-3-642-13562-0

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00535784"><analytic>
<author><persName><forename>Guillaume</forename><surname>Bonfante</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">CARTE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Florian</forename><surname>Deloup</surname></persName>
<affiliation>
<orgName type="laboratory">IMT</orgName>
<orgName type="team">Institut de Mathématiques de Toulouse</orgName>
<country>FR</country>
<orgName type="institution">Université Paul Sabatier [UPS] - Toulouse III</orgName>
<orgName type="institution">Université Toulouse le Mirail - Toulouse II</orgName>
<orgName type="institution">Université des Sciences Sociales - Toulouse I</orgName>
<orgName type="institution">Institut National des Sciences Appliquées (INSA) - Toulouse</orgName>
<orgName type="institution">CNRS : UMR5219</orgName>
</affiliation>
</author>
<title type="main" level="a">Complexity invariance of real interpretations</title></analytic><monogr><meeting>7th Annual Conference on Theory and Applications of Models of Computation - TAMC 2010</meeting><imprint><publisher>Springer</publisher><pubPlace><settlement>Prague</settlement><country>Czech Republic</country></pubPlace><biblScope type="publicationDate">2010-03-27</biblScope><biblScope type="vol">6108</biblScope><biblScope type="pp">139-150</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-642-13562-0</idno><idno type="HALid">http://hal.inria.fr/inria-00535784</idno><idno type="HALFile">http://hal.inria.fr/inria-00535784/PDF/final.pdf</idno></biblStruct>
</listBibl>
</listBibl>