Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $n$, a divisor $k$ of $n$, and a subset $S \subset \mathbb{Z}\_n$ of size k. The problem is to decide whether $\mathbb{Z}\_n$ can be covered with $n/k$ cyclic translations of $S$, i.e. sets of the form $S+a\_i$ for various $a\_i \in \mathbb{Z}\_n$. This is simply a special case of the NP-complete EXACT COVER problem---namely, where the available sets are all cyclic shifts of each other, and where all cyclic shifts are available. My suspicion is that the special case is already NP-complete, while Ernest suspects that an $n^{O(1)}$ time algorithm exists. I searched Google (and Garey&Johnson) and couldn't find leads -- would appreciate any thoughts or references!



Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set -- easy? NP-complete?
Here are a few references; the right keywords seem to be "tiling by translation" or a "factorization of a group":


Mihail N. Kolountzakis and Máté Matolcsi, Algorithms for translational tiling, Journal of Mathematics and Music, 3:2 (2009), 85-97, <https://doi.org/10.1080/17459730903040899>


Mihail N. Kolountzakis and Mate Matolcsi, Tilings by translation (2010),
<https://arxiv.org/abs/1009.3799>


See also the following MO question about a more general problem about covering density (2013):
[Is this a known combinatorial problem?](https://mathoverflow.net/questions/137219/is-this-a-known-combinatorial-problem)


