Maximum likelihood is one of the most widely used techniques to infer evolutionary histories. Although it is thought to be intractable, a proof of its hardness has been lacking. Here, we give a short proof that computing the maximum likelihood tree is NP-hard by exploit... View more
 L. Addario-Berry, B. Chor, M. T. Hallett, J. Lagergren, A. Panconesi, and T. Wareham, “Ancestral Maximum Likelihood of Evolutionary Trees is Hard,” Journal of Bioinformatics and Computational Biology, vol. 2, no. 2, pp. 257-271, 2004.
 R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, and M. Thorup, “On the approximability of numerical taxonomy (fitting distances by tree metrics),” SIAM Journal on Computing, vol. 28, pp. 1073-1085, 1999.
 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation, Springer, Berlin, 1999.
 J. Cavender, “Taxonomy with confidence,” Mathematical Biosciences, vol. 40, pp. 271-280, 1978.
 B. Chor and T. Tuller, “Maximum Likelihood of Evolutionary Trees is Hard,” In: Proceedings of the 9th International Conference on Computational Molecular Biology (RECOMB 2005), ACM Press, Cambridge, 2005.
 A. Clementi, and L. Trevisan, “Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints,” Theor. Comput. Sci., vol. 225, no. 1-2, pp. 113-128, 1999.
 W. Day, D. Jonhson, and D. Sankoff, “The computational complexity of inferring rooted phylogenies by parsimony,” Mathematical Biosciences, vol. 81, pp. 33-42, 1986.
 W. Day and D. Sankoff, “The computational complexity of inferring phylogenies by compatibility,” Systematic Zoology, vol. 35, pp. 224-229, 1986.
 A. W. F. Edwards and L. L. Cavalli-Sforza, “Reconstruction of evolutionary trees,” In: Phenetic and Phylogenetic Classification, eds. V. H. Heywood and J. McNeill, Systematics Association, London, vol. 6, pp. 67-76, 1964.
 J. S. Farris, “A probability model for inferring evolutionary trees,” Systematic Zoology, vol. 22, pp. 250-256, 1973.