Coxeter groups and nonuniform complexity (Q1814266)

For any Coxeter group \(W\) a faithful information system with object set \(W\) and the decision graph computing a mapping \(f: W\to 2\) are constructed. Almost all functions \(f\) are hard to compute. The complexity of \(f\) is a lower bound for some complexity of an arbitrary extension \(f\). The condition complex \(\text{Cond}(I)\) of an information system \(I\) is defined. If \(T\) is the set of reflections of \(W\), then \(\text{Cond}(I)\) is a triangulation of a \((\#T-1)\)-dimensional sphere and the Coxeter complex is embedded into \(\text{Cond}(I)\). The decision graphs for symmetric groups are related to sorting by comparison. Symmetric and monotone functions on Coxeter groups of type \(A_ n\), \(B_ n\), \(D_ n\) are in fact functions on graphs, bipartite graphs and directed graphs, respectively.