Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard

A reduced word of the longest permutation $w_0\in S_m$, taken up to commutations, encodes a wiring diagram of $m$ pseudolines, and a braid move $σ_iσ_{i+1}σ_i\leftrightarrowσ_{i+1}σ_iσ_{i+1}$ flips one of its triangles. We prove that deciding whether two wiring diagrams are within a given braid-move