We investigate the relationship between template metaprogramming and computational complexity, showing how C++ templates characterize the class of polynomialtime computable function, by means of template recursion and specialization. Hence, standard C++ compilers can be used to certify polytime-bounded programs.

Template Metaprogramming, Partial Evaluation and Computational Complexity Classes

COVINO, Emanuele;PANI, Giovanni
2010-01-01

Abstract

We investigate the relationship between template metaprogramming and computational complexity, showing how C++ templates characterize the class of polynomialtime computable function, by means of template recursion and specialization. Hence, standard C++ compilers can be used to certify polytime-bounded programs.
2010
1-60132-142-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11586/18743
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact