The Word Problem for Products of Symmetric Groups
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908409084772352 |
|---|---|
| author | Simon, Hans U. |
| author_facet | Simon, Hans U. |
| contents | 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'' $X_1,\ldots,X_m \seq \{1,\ldots,n\}$ and a permutation $τ$ on $\{1,\ldots,n\}$. The sets $X_1,\ldots,X_m$ specify a subset of the symmetric group $\cS_n$ 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 WPPSG$_0$ is the restriction of WPPSG to specification sets all of which are sets of consecutive integers. The subproblem WPPSG$_1$ is the restriction of WPPSG to specification sets which have the Consecutive Ones Property. The subproblem WPPSG$_2$ is the restriction of WPPSG to specification sets which have what we call the Weak Consecutive Ones Property. WPPSG$_1$ is more general than WPPSG$_0$ and WPPSG$_2$ is more general than WPPSG$_1$. But the efficient algorithms that we use for solving WPPSG$_1$ and WPPSG$_2$ have, as a sub-routine, the efficient algorithm for solving WPPSG$_0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13655 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Word Problem for Products of Symmetric Groups Simon, Hans U. Computational Complexity 68Q25 F.2.2 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'' $X_1,\ldots,X_m \seq \{1,\ldots,n\}$ and a permutation $τ$ on $\{1,\ldots,n\}$. The sets $X_1,\ldots,X_m$ specify a subset of the symmetric group $\cS_n$ 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 WPPSG$_0$ is the restriction of WPPSG to specification sets all of which are sets of consecutive integers. The subproblem WPPSG$_1$ is the restriction of WPPSG to specification sets which have the Consecutive Ones Property. The subproblem WPPSG$_2$ is the restriction of WPPSG to specification sets which have what we call the Weak Consecutive Ones Property. WPPSG$_1$ is more general than WPPSG$_0$ and WPPSG$_2$ is more general than WPPSG$_1$. But the efficient algorithms that we use for solving WPPSG$_1$ and WPPSG$_2$ have, as a sub-routine, the efficient algorithm for solving WPPSG$_0$. |
| title | The Word Problem for Products of Symmetric Groups |
| topic | Computational Complexity 68Q25 F.2.2 |
| url | https://arxiv.org/abs/2506.13655 |