2025/06/16 by Hans Ulrich Simon, Simon, Hans U.
Computer Science · Mathematics · #68Q25 #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #Finite Group Theory Research #Geometric and Algebraic Topology #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2506.13655
openalex publication_date 2025/06/16 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28
The word problem for products of symmetric groups (WPPSG) is a well-known NP-complete problem. An input instance of this problem consists of ``specification sets'' X1,…,Xm \seq \1,…,n\ and a permutation τ on \1,…,n\. The sets X1,…,Xm specify a subset of the symmetric group \cSn and the question is whether the given permutation τ is a member of this subset. We discuss three subproblems of WPPSG and show that they can be solved efficiently. The subproblem WPPSG0 is the restriction of WPPSG to specification sets all of which are sets of consecutive integers. The subproblem WPPSG1 is the restriction of WPPSG to specification sets which have the Consecutive Ones Property. The subproblem WPPSG2 is the restriction of WPPSG to specification sets which have what we call the Weak Consecutive Ones Property. WPPSG1 is more general than WPPSG0 and WPPSG2 is more general than WPPSG1. But the efficient algorithms that we use for solving WPPSG1 and WPPSG2 have, as a sub-routine, the efficient algorithm for solving WPPSG0.