Finding the maximum a posteriori probability (MAP) in a Bayesian taxonomic key is NP-hard

As an alternative to dichotomous keys, tabular keys are used for taxonomic identification. With the use of computers, keys based on the Bayes formula can also be made available more widely. For the development of a key, the maximum a posterior probability (MAP) for a taxon is important because it allows to evaluate the quality of a key. If it is low, the taxon is hard to distinguish from other taxa. In this paper, we show that finding MAP in a Bayesian key is NP-hard. Estimates for MAP or other measures have to be used for the estimation of the quality of a Bayesian key.