The complexity of intersecting subproducts with subgroups in Cartesian powers

2021/01/15 by Pim Spelier, Spelier, Pim
Computer Science · Mathematics · #20D60 #68Q17 #Abelian group #Advanced Graph Theory Research #Algebra over a field #Algebraic number #Cartesian product #Combinatorics #Computability, Logic, AI Algorithms #Coset #Discrete mathematics #FOS: Mathematics #Group Theory (math.GR) #Intersection (aeronautics) #Limits and Structures in Graph Theory #Mathematics #Natural number #Pure mathematics

paper · pdf · doi:10.48550/arxiv.2101.06157

openalex publication_date 2021/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Given a finite abelian group G and t∈ ℕ, 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].

Related

• Intersective sets over abelian groups
• Subgroup and Coset Intersection in abelian-by-cyclic groups
• Quasipolynomial bounds for the corners theorem
• Algorithmic problems for free-abelian times free groups
• Decision problems and profinite completions of groups