# Calculating lexicase selection probabilities is NP-Hard

arXiv: https://arxiv.org/abs/2301.06724 · HTML: https://mlsanity.com/paper/2301.06724/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jan 2023.

## Built on by (most cited first, 3 of 3)

- [Probabilistic Lexicase Selection](https://mlsanity.com/paper/2305.11681/) (2023)
- [Particularity](https://mlsanity.com/paper/2306.06812/) (2023)
- [DALex: Lexicase-like Selection via Diverse Aggregation](https://mlsanity.com/paper/2401.12424/) (2024)

## Abstract (arXiv)

Calculating the probability of an individual solution being selected under lexicase selection is an important problem in attempts to develop a deeper theoretical understanding of lexicase selection, a state-of-the art parent selection algorithm in evolutionary computation. Discovering a fast solution to this problem would also have implications for efforts to develop practical improvements to lexicase selection. Here, I prove that this problem, which I name lex-prob, is NP-Hard. I achieve this proof by reducing SAT, a well-known NP-Complete problem, to lex-prob in polynomial time. This reduction involves an intermediate step in which a popular variant of lexicase selection, epsilon-lexicase selection, is reduced to standard lexicase selection. This proof has important practical implications for anyone needing a fast way of calculating the probabilities of individual solutions being selected under lexicase selection. Doing so in polynomial time would be incredibly challenging, if not all-together impossible. Thus, finding approximation algorithms or practical optimizations for speeding up the brute-force solution is likely more worthwhile. This result also has deeper theoretical implications about the relationship between epsilon-lexicase selection and lexicase selection and the relationship between lex-prob and other NP-Hard problems.