A Tool for the Evaluation of the Complexity of Programs Using C++ Templates
The authors investigate the relationship between C++ template metaprogramming and computational complexity, showing how templates characterize the class of polynomial-time computable functions, by means of template recursion and specialization. Hence, standard C++ compilers can be used as a tool to certify polytime-bounded programs. According to, template metaprograms consist of classes of templates operating on numbers and types as a data. Algorithms are expressed using template recursion as a looping construct and template specialization as a conditional construct. Template recursion involves the use of class templates in the construction of its own member type or member constant.