Algorithmic complexity: three NP- hard problems in computational statistics

Abstract

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.

Keywords:

• Algorithm
• algorithmic complexity
• n p-complete
• n p-hard
• cluster analysis
• regression
• subset selection
• design of experiments
• d-optimal

†Preqent address: British Tclecom Headquarters. Cheapside House, Room 213, London EC2V 6JH, Great Britain.

†Preqent address: British Tclecom Headquarters. Cheapside House, Room 213, London EC2V 6JH, Great Britain.

Notes

†Preqent address: British Tclecom Headquarters. Cheapside House, Room 213, London EC2V 6JH, Great Britain.