ON THE COMPLEXITY OF LINEAR-QUADRATIC CONTROL

This paper presents an analysis of the computational complexity of the linear quadratic control models commonly used in Economics. These mod els differ in the statistical assumptions concerning the coefficients. The most common assumptions are fixed unknown, fixed known and indepe ndent random. A fourth model to be considered is the MacRae approximat ion. These four models have a nested structure. The computational comp lexity of the first is transfinite. The computational complexity of th e second is linear in the time horizon, T and has the same computation al complexity in the number of states, n as that for matrix multiplica tion of (n X n)-matrices. The computational complexity of the third is n4T. The computational complexity of each iteration of the MacRae app roximation is n4T.