1,720,997 research outputs found
Complexity certification of C++ templates
No full textAny partial recursive function can be computed at compile time, using C++ templates to define primitive recursion, composition, and minimalization. We define a sub-language based on C++ templates, which characterizes the set of functions computable by a Turing machine with time bounded by a polinomial. This language can be used as a form of complexity certification of programs
Template Metaprogramming, Partial Evaluation and Computational Complexity Classes
No full textWe 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
Predicative recursion, diagonalization, and slow-growing hierarchies of time-bounded programs
Full text linkWe define a version of predicative recursion, a related programming language, and a hierarchy of classes of programs that represents a resource-free characterization of register machines computing their output within polynomial time O(n^k), for each finite k. Then, we introduce an operator of diagonalization, that allows us to extend the previous hierarchy and to capture the register machines with computing time
bounded by an exponential limit O(n^n^k ). Finally, by means of a restriction on composition of programs, we characterize the register machines with a polynomial bound imposed over time and space complexity, simultaneously
A specialized recursive language for capturing time-space complexity classes
Full text linkWe provide a resource-free characterization of register machines that computes their output within polynomial time O(n^k), by defining our version of predicative recursion and a related recursive programming language. Then, by means of some restriction on composition of programs, we define a programming language that characterize the register machines with a polynomial bound imposed over time and
space complexity, simultaneously. A simple syntactical analysis allows us to evaluate the complexity of a program written in
these languages
- …
