An Invitation to "Fine-grained Complexity of NP-Complete Problems"
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908754016993280 |
|---|---|
| author | Nederlof, Jesper |
| author_facet | Nederlof, Jesper |
| contents | Assuming that P is not equal to NP, the worst-case run time of any algorithm solving an NP-complete problem must be super-polynomial. But what is the fastest run time we can get? Before one can even hope to approach this question, a more provocative question presents itself: Since for many problems the naive brute-force baseline algorithms are still the fastest ones, maybe their run times are already optimal?
The area that we call in this survey "fine-grained complexity of NP-complete problems" studies exactly this question. We invite the reader to catch up on selected classic results as well as delve into exciting recent developments in a riveting tour through the area passing by (among others) algebra, complexity theory, extremal and additive combinatorics, cryptography, and, of course, last but not least, algorithm design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05044 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Invitation to "Fine-grained Complexity of NP-Complete Problems" Nederlof, Jesper Data Structures and Algorithms Computational Complexity Assuming that P is not equal to NP, the worst-case run time of any algorithm solving an NP-complete problem must be super-polynomial. But what is the fastest run time we can get? Before one can even hope to approach this question, a more provocative question presents itself: Since for many problems the naive brute-force baseline algorithms are still the fastest ones, maybe their run times are already optimal? The area that we call in this survey "fine-grained complexity of NP-complete problems" studies exactly this question. We invite the reader to catch up on selected classic results as well as delve into exciting recent developments in a riveting tour through the area passing by (among others) algebra, complexity theory, extremal and additive combinatorics, cryptography, and, of course, last but not least, algorithm design. |
| title | An Invitation to "Fine-grained Complexity of NP-Complete Problems" |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2601.05044 |