Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice Journal: Theoretical Computer Science
Mircea-Adrian Digulescu · 2026
Read Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice Journal: Theoretical Computer Science by Mircea-Adrian Digulescu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16418.txt.
Introduction
Digulescu proposes a framework for reasoning about algorithms when input size has a known upper bound, rather than growing without limit. Adapting complexity ideas to this finite setting, he offers results and a method for finding a suitable algorithm for the finite version of a hard problem, where one exists. He argues that finite cases should prove easier than general cases. He sketches ideas for three hard problems: satisfiability in 3CNF form, string compression and integer factorization. The paper is a proposal, not a claimed general solution.
Catalog record
| CREATOR | Mircea-Adrian Digulescu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132275 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16418
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice Journal: Theoretical Computer Science Mircea-Adrian Digulescu Abstract 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. However, this is the precise opposite of what is actually needed in practice. Effectively solving some real-world problem entails identifying an algorithm which works well for all (or some) inputs up to some fixed upper bound dictated by the concrete practical application. Such an algorithm may be distinct from the one which solves the general case. Furthermore, a general case algorithm may not exist at all or finding it might prove painstakingly hard for the human mind. Fortunately, in practice all that is needed is one which works on the finite cases involved in the real world situations, not one which can, unaltered, solve any input correctly. 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 3CNF-SAT, String Compression and Integer Factorization. Fifthly, we discuss the significance of the theory and methods introduced in this paper - noting among other things that they can be used to automatically determine that either (i) P = N P P=NP , (ii) P ≠ N P P\neq NP or (iii) we don’t really care about the distinction for practical purposes. Finally, we present four directions for immediate further research and formulate an open question which, when answered will, for all practical purposes, decide P = N P P=NP . Enhancing the way Computer Scientists reason about hard problems is ultimately the single most important contribution we claim for this paper. 1 Introduction Until now, we as Computer Scientists have almost exclusively concerned ourselves with finding algorithms to solve interesting problems in the general case. That is to identify a single algorithm - some fixed finite sequence of lines of code - which solves said problem for any input. We then reason about upper time and space bounds for such an algorithm in terms of asymptotical complexity with regard to the input size in bits (or some general unbounded parameter which describes the difficulty of the input). When we are unable to find an algorithm suitable to our desires, we can reason about the constraints to which such - if it exists - must conform, in terms of lower-bounds. Furthermore, we can go on and analyze the relation between the relative hardness of problems - even of those for which we do not yet have a satisfactory solution - by clustering them into complexity classes and then proceeding to examine the relationships between these. In 2005 there were about 417 complexity classes in the Complexity Zoo [ 1 ] . As of 2019, the number has grown to about 544 classes currently being investigated by humanity. However, they all pertain to solving some hard problem correctly and efficiently for all inputs, no matter how large. A large number of problems, including SAT and all NP-Complete ones, integer factorization, solving stochastic games, all PSPACE-Complete problems and all problems in EXPTIME and above, as well as some mysterious ones like breaking AES encryption do not have any known efficient algorithm despite decades of research. These add to problems which are known not to admit any algorithm at all to solve them in the general case, including Kolmogorov complexity and the Busy Beaver Game. Some of the others are suspected to not to admit such, but wheatear this is actually true or not is yet unknown. Nevertheless, a large number of instances of many of such problems are actually solvable in practice. Modern SAT Solvers [ 2 ] can solve problems over up to millions of variables and a large number of those over tens of thousands [ 3 ] [ 4 ] . There is no presently known method of deriving an instance of a SAT problem which is hard to solve by any heuristic (although finding easy cases of arbitrary size can be done). In fact, not even a theoretical framework exists to reason about such cases, despite numerous published empirical studies. The incomputable Busy Beaver problem itself has been solved for the two symbol game, up to 4 states inclusively [ 5 ] . There is an apparent discrepancy between how hard a problem seems to be in the general case (at least for the human mind) and how easy it is for at least some practical cases, which are the ones of actual concern to us. As such, it is time to turn our attention to studying actual instances of cases of hard problems - in particular those which might appear in practice (and are thus almost always of bounded input size). Investigating these might sometimes lead to efficient algorithms for all real-world needs, or even to the discovery of the general case solution. Until now, computer science theory has paid little to no attention to finite algorithmics. The very foundational tool used to reason about algorithms - asymptotic complexity of a function, works by definition only for the limit to infinity. Under existing theory, all practical instances of a problem - which almost always entail some bound on input size - are trivially solvable in O(1) . This includes computation of incomputable functions, without inclusion of proofs of correctness. In this paper we remedy this lacking of the current complexity theory by introducing finite algorithmics. We also present some noteworthy elementary results formulated under it. 1.1 Prior work As far as we know there is no theoretical prior work concerning finite algorithmics, as we are just now introducing the field. Results exists which can, in retrospect, be regarded as part of field of finite algorithmics however. They can be found in the following domains: Artificial Intelligence and Machine Learning (there most problems solved have bounded input size by formulation), Heuristic Solvers for NP-Complete Problems (such as SAT Solvers) and to some extent Cryptography (since most cyphers have fixed key and block sizes). Nevertheless, even within these fields there has been to the best of our knowledge no systematic effort to date to introduce a theory which would allow formal reasoning about relative performance of various algorithms and relationships between various classes of problems with regard to a fixed upper bound on input size. The study of the P/poly complexity class can be considered tangential to this work. We will discuss its relationship to some of the other complexity classes we introduce. 1.2 Overview of this paper The rest of this paper is organized as follows. In Section 3 we introduce the theory related to Finite