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!
|
Table of 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].