Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908974944616448 |
|---|---|
| author | Digulescu, Mircea-Adrian |
| author_facet | Digulescu, Mircea-Adrian |
| contents | Until now, Computer Scientists have concerned themselves with identifying efficient algorithms for solving the general case of some problem -- that is finding one which performs well when the size of the input tends to infinity. In this paper, we first introduce a theoretical framework for reasoning about finite algorithmics. It allows familiar concepts such as asymptotic complexity to be adapted to the case where the input size is bounded from above. We also present some elementary results within this theory. Secondly, we present a generic approach for automatically discovering an adequate algorithm for the finite case of some hard problem -- if one exists. Thirdly, we argue why we expect the finite case of hard problems to be easier than the general case. Fourthly, we present some relevant ideas specific to three hard problems, namely 3CNFSAT, String Compression and Integer Factorization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16418 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice Digulescu, Mircea-Adrian Computational Complexity Until now, Computer Scientists have concerned themselves with identifying efficient algorithms for solving the general case of some problem -- that is finding one which performs well when the size of the input tends to infinity. In this paper, we first introduce a theoretical framework for reasoning about finite algorithmics. It allows familiar concepts such as asymptotic complexity to be adapted to the case where the input size is bounded from above. We also present some elementary results within this theory. Secondly, we present a generic approach for automatically discovering an adequate algorithm for the finite case of some hard problem -- if one exists. Thirdly, we argue why we expect the finite case of hard problems to be easier than the general case. Fourthly, we present some relevant ideas specific to three hard problems, namely 3CNFSAT, String Compression and Integer Factorization. |
| title | Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.16418 |