Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2101.06157 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916815788048384 |
|---|---|
| author | Spelier, Pim |
| author_facet | Spelier, Pim |
| contents | Given a finite abelian group $G$ and $t\in \mathbb{N}$, there are two natural types of subsets of the Cartesian power $G^t$; namely, Cartesian powers $S^t$ where $S$ is a subset of $G$, and (cosets of) subgroups $H$ of $G^t$. A basic question is whether two such sets intersect. In this paper, we show that this decision problem is NP-complete. Furthermore, for fixed $G$ and $S$ we give a complete classification: we determine conditions for when the problem is NP-complete, and show that in all other cases the problem is solvable in polynomial time. These theorems play a key role in the classification of algebraic decision problems in finitely generated rings developed in [Spe21]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2101_06157 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The complexity of intersecting subproducts with subgroups in Cartesian powers Spelier, Pim Group Theory 20D60, 68Q17 Given a finite abelian group $G$ and $t\in \mathbb{N}$, there are two natural types of subsets of the Cartesian power $G^t$; namely, Cartesian powers $S^t$ where $S$ is a subset of $G$, and (cosets of) subgroups $H$ of $G^t$. A basic question is whether two such sets intersect. In this paper, we show that this decision problem is NP-complete. Furthermore, for fixed $G$ and $S$ we give a complete classification: we determine conditions for when the problem is NP-complete, and show that in all other cases the problem is solvable in polynomial time. These theorems play a key role in the classification of algebraic decision problems in finitely generated rings developed in [Spe21]. |
| title | The complexity of intersecting subproducts with subgroups in Cartesian powers |
| topic | Group Theory 20D60, 68Q17 |
| url | https://arxiv.org/abs/2101.06157 |