Algorithmic complexity: three NP - hard problems in computational statistics

A theory of algorithmic complexity from computer science allows one to examine the properties of algorithms for the solution of computational problems and, in particular, the relationship between the size of an instance of the generic problem and the time required for computation The theory identifies certain problems as n p- complete or n p-hard, two classes of problems thought to be intractable. We show that three problems from computational statistics are n p- hard: cluster analysis, subset selection in regression and D-optimal exact design of experiments.