AND

In systematics, parsimony methods construct phylogenies, or evolutionary trees, in which characters evolve with the least evolutionary change. The Camin-Sokal and Do110 parsimony criteria are used to construct phylogenies from discrete characters. Variations of these problems depend on whether characters are: cladistic (rooted) or qualitative (un-rooted): binary (two states) or multistate (more than one state). The computational cost of known algorithms that guarantee optimal solutions to these problgms increases exponen-tially with problem size; practical computational considerations restrict the use of such algorithms to analyzing problems of small size. We establish that the basic variants of these problems are all NP-complete and thus are so difficult computationally that efficient optimal algorithms are unlikely to exist for them. 1