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 asnp- complete ornp-hard, two classes of problems thought to be intractable. We show that three problems from computational statistics arenp- hard: cluster analysis, subset selection in regression andD-optimal exact design of experiments.
展开▼
