Recognizing Sumsets is NP-Complete
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917818119749632 |
|---|---|
| author | Abboud, Amir Fischer, Nick Safier, Ron Wallheimer, Nathan |
| author_facet | Abboud, Amir Fischer, Nick Safier, Ron Wallheimer, Nathan |
| contents | Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set $S$ is a sumset, i.e. whether there is a set $A$ such that $A+A=S$. Granville suggested an algorithm that takes exponential time in the size of the given set, but can we do polynomial or even linear time? This basic computational question is indirectly asking a fundamental structural question: do the special characteristics of sumsets allow them to be efficiently recognizable? In this paper, we answer this question negatively by proving that the problem is NP-complete. Specifically, our results hold for integer sets and over any finite field. Assuming the Exponential Time Hypothesis, our lower bound becomes $2^{Ω(n^{1/4})}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18661 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recognizing Sumsets is NP-Complete Abboud, Amir Fischer, Nick Safier, Ron Wallheimer, Nathan Data Structures and Algorithms Computational Complexity Discrete Mathematics Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set $S$ is a sumset, i.e. whether there is a set $A$ such that $A+A=S$. Granville suggested an algorithm that takes exponential time in the size of the given set, but can we do polynomial or even linear time? This basic computational question is indirectly asking a fundamental structural question: do the special characteristics of sumsets allow them to be efficiently recognizable? In this paper, we answer this question negatively by proving that the problem is NP-complete. Specifically, our results hold for integer sets and over any finite field. Assuming the Exponential Time Hypothesis, our lower bound becomes $2^{Ω(n^{1/4})}$. |
| title | Recognizing Sumsets is NP-Complete |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2410.18661 |