  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.
