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