Compile-time Computation of Polytime Functions

Emanuele Covino (Università di Bari, Italy)

Giovanni Pani (Università di Bari, Italy)

Daniele Scrimieri (Università di Bari, Italy)

Abstract: We investigate the computational power of C++ compilers. In particular, it is known that any partial recursive function can be computed at compile time, using the template mechanism to de¯ne primitive recursion, composition, and minimalization. We show that polynomial time computable functions can be computed at compile-time using the same mechanism, together with template specialization.

Keywords: C++ templates, polytime computable functions, static computation

Categories: D.3, F.1.3