License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.62
URN: urn:nbn:de:0030-drops-49042
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4904/
Go to the corresponding LIPIcs Volume Portal

Avanzini, Martin ; Dal Lago, Ugo

On Sharing, Memoization, and Polynomial Time

pdf-format:
4.pdf (0.8 MB)

Abstract

We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natural cost model in which lookup for an already computed result has no cost is indeed invariant. As a corollary, we then prove that the most general notion of ramified recurrence is sound for polynomial time, this way settling an open problem in implicit computational complexity.

BibTeX - Entry

@InProceedings{avanzini_et_al:LIPIcs:2015:4904,
  author =	{Martin Avanzini and Ugo Dal Lago},
  title =	{{On Sharing, Memoization, and Polynomial Time}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{62--75},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4904},
  URN =		{urn:nbn:de:0030-drops-49042},
  doi =		{10.4230/LIPIcs.STACS.2015.62},
  annote =	{Keywords: implicit computational complexity, data-tiering, polynomial time}
}

Keywords: implicit computational complexity, data-tiering, polynomial time
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI