There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words for elements of $W$ that determines whether or not the two words are words for the same element of $W$ (this can be seen, for example, using the numbers game). The corresponding enumeration problem, counting the number of words that are reduced words for the same element, is therefore in the complexity class #P.
The problem of enumerating the linear extensions of a finite partially ordered set is #P-complete. We can reduce this problem to the enumeration of reduced words in a Coxeter group in polynomial time by taking $S$ to be the partially ordered set itself, letting $ss'$ be of infinite order if $s$ and $s'$ are distinct comparable elements, letting $(ss')^2=1$ if $s$ and $s'$ are incomparable, and choosing our reduced word to be the elements listed in the order of some linear extension. Therefore the problem of enumerating reduced words is #P-complete.
How can we reduce the reduced word enumeration problem in polynomial time to a more familiar #P-complete problem?
