C++ Truths

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 solut...