Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
For computer scientists, this work proposes a new perspective on algorithm design for hard problems when input size is bounded, potentially enabling practical solutions for NP-complete problems.
This paper introduces a theoretical framework for finite algorithmics, adapting asymptotic complexity to bounded input sizes, and presents a generic approach for automatically discovering efficient algorithms for hard problems in the finite case. The authors argue that the finite case is easier and provide ideas for 3CNFSAT, String Compression, and Integer Factorization.
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.