Here you will find a short C++ program that takes more than 24 hrs to compile on a dedicated dual processor, 1GB memory machine!! Here we go...

template<int Depth, int A, typename B>

struct K17 {

static const int x =

K17 <Depth+1, 0, K17<Depth,A,B> >::x

+ K17 <Depth+1, 1, K17<Depth,A,B> >::x

+ K17 <Depth+1, 2, K17<Depth,A,B> >::x

+ K17 <Depth+1, 3, K17<Depth,A,B> >::x

+ K17 <Depth+1, 4, K17<Depth,A,B> >::x;

};

template <int A, typename B>

struct K17 <16,A,B> { static const int x = 1;

};

static const int z = K17 <0,0,int>::x;

int main(void) { }

Source: C++ Templates are Turing Complete by Todd L. Veldhuizen

This program is taken from the above paper which takes unreasonably long to compile. I belive, a simple dynamic programming solution will reduce the exponential time required by this program to compile to polynomial time. I also believe, it might be quite difficult to apply dynamic programming solution, in general,…

template<int Depth, int A, typename B>

struct K17 {

static const int x =

K17 <Depth+1, 0, K17<Depth,A,B> >::x

+ K17 <Depth+1, 1, K17<Depth,A,B> >::x

+ K17 <Depth+1, 2, K17<Depth,A,B> >::x

+ K17 <Depth+1, 3, K17<Depth,A,B> >::x

+ K17 <Depth+1, 4, K17<Depth,A,B> >::x;

};

template <int A, typename B>

struct K17 <16,A,B> { static const int x = 1;

};

static const int z = K17 <0,0,int>::x;

int main(void) { }

Source: C++ Templates are Turing Complete by Todd L. Veldhuizen

This program is taken from the above paper which takes unreasonably long to compile. I belive, a simple dynamic programming solution will reduce the exponential time required by this program to compile to polynomial time. I also believe, it might be quite difficult to apply dynamic programming solution, in general,…