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]\}$.

$\endgroup$
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.

$\endgroup$
  • $\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 Oct 20 '18 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 Oct 21 '18 at 3:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.