Geodesic
LLL-solver
Matematičeskoe modelirovanie, Tome 24 (2012) no. 12, pp. 43-48

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we overview the possible way to solve for the “reasonable time” the NP-complete problems representatives called LLL-solver. This way is linked to the knapsack problem solving method offered by Lagarias and Odlyzko. Proved: the existence of such polynomial transformation of the 3-SAT problem to the knapsack problem that the image of the 3-SAT problem is situated in the area of knapsack with the density $d$, where $C$ is any given constant less or equal than $3(\log_27)^{-1}$. Introduced: the notion of the algorithm validity function. Showed: the results of the computer experiments on the calculation of the LLL-solver validity functions.
Keywords: LLL-algorithm, Knapsack problem, Lagarias–Odlyzko method. 
@article{MM_2012_24_12_a7,
     author = {D. M. Murin},
     title = {LLL-solver},
     journal = {Matemati\v{c}eskoe modelirovanie},
     pages = {43--48},
     publisher = {mathdoc},
     volume = {24},
     number = {12},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MM_2012_24_12_a7/}
}
TY  - JOUR
AU  - D. M. Murin
TI  - LLL-solver
JO  - Matematičeskoe modelirovanie
PY  - 2012
SP  - 43
EP  - 48
VL  - 24
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MM_2012_24_12_a7/
LA  - ru
ID  - MM_2012_24_12_a7
ER  - 
%0 Journal Article
%A D. M. Murin
%T LLL-solver
%J Matematičeskoe modelirovanie
%D 2012
%P 43-48
%V 24
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MM_2012_24_12_a7/
%G ru
%F MM_2012_24_12_a7
D. M. Murin. LLL-solver. Matematičeskoe modelirovanie, Tome 24 (2012) no. 12, pp. 43-48. http://geodesic.mathdoc.fr/item/MM_2012_24_12_a7/