2
$\begingroup$

Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences.

For a positive integer $m$, system $A$ is called a $m$-cover of $\mathbb{N}$, if every natural number is covered by $A$ at least $m$ times.

My question is as follows: is there an efficient algorithm that given $A$ and $m$ decides if $A$ is a $m$-cover?

By an efficient algorithm I would perhaps mean an algorithm with the running time polynomial in $k$, $m$, and $\max\{a_i,b_i~|~i\in[k]\}$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

In 1973， L. J. Stockmeyer and A. R. Meyer [Proc. 5th. Ann. ACM Symp. on Theory of Computing, Assoc. for Computing Machinery] proved that the question whether a given system $A=\{a_i+b_i\mathbb N\}_{i=1}^k$ is a cover of $\mathbb Z$ (i.e., $1$-cover) is co-NP-complete. Thus NP=P if and only if we can decide whether $A=\{a_i+b_i\mathbb N\}_{i=1}^k$ is a cover of $\mathbb Z$ in polynomial time. Whether NP=P or not is a famous open problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Zhi-Wei Sun, thanks for your answer! Unfortunately, I'm not enough familiar with the complexity theory to quickly spot the relevant results. I would be grateful if you could point out which of their problems corresponds to 1-cover and which of the statements proves co-NP-completeness. (I was reading this goo.gl/8HsxQm version of the above paper) $\endgroup$
    – Victor
    Commented Oct 20, 2018 at 14:09
  • 1
    $\begingroup$ @Victor Here I provide you an excellent introductory book to NP-completeness where Stockmeyer and Meyer's result was included: M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman, 1979. ISBN 0-7167-1045-5. $\endgroup$
    – Zhi-Wei Sun
    Commented Oct 21, 2018 at 3:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .