Geodesic
LLL-solver
Matematičeskoe modelirovanie, Tome 24 (2012) no. 12, pp. 43-48 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2012},
     volume = {24},
     number = {12},
     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
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
%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/

[1] Moskewicz M., Madigan C., Zhao Y., Zhang L., Malik S., “Chaff: Engineering an Efficient SAT Solver”, Proc. 38th Design Automation Conference, 2001

[2] Goldberg E., Novikov Y., “BerkMin: A fast and robust SAT-solver”, Design, Automation, and Test in Europe, 2002, 142–149

[3] Zaikin O. S., Parallelnaya tekhnologiya resheniya SAT-zadach i ee realizatsiya v vide paketa prikladnykh programm, dissertatsiya ... kand. tekh. nauk, IDSTU SO RAN, Irkutsk, 2008

[4] Davis M., Putnam H., “A computing procedure for quantification theory”, Journal of the ACM, 1960, no. 7, 201–215 | DOI | MR | Zbl

[5] Davis M., Logemann G., Loveland D., “A machine program for theorem-proving”, Comm. of the ACM, 5:7 (1962), 394–397 | DOI | MR | Zbl

[6] Odlyzko A. M., Lagarias J. C., “Solving Low-Density Subset Sum Problems”, Journal of the Association for Computing Machinery, 32:1 (1985), 229–246 | DOI | MR | Zbl

[7] Coster M. J., Joux A., LaMacchia B. A., Odlyzko A. M., Schnorr C.-P., Stern J., “Improved low-density subset sum algorithms”, Computational Complexity, 1992, no. 2, 111–128 | DOI | MR | Zbl

[8] Murin D. M., “O nekotorykh svoistvakh obrazov transformirovannykh zadach”, Prikladnaya diskretnaya matematika, 2012, no. 3, 96–102

[9] Kormen T., Leizerson Ch., Rivest R., Shtain K., Algoritmy: postroenie i analiz, Vilyams, M., 2005, 1296 pp.

[10] Vasilenko O. N., Teoretiko-chislovye algoritmy v kriptografii, MTsNMO, M., 2006, 336 pp.

[11] Vinogradov I. M. (red.), Matematicheskaya entsiklopediya, v. 3, Sovetskaya entsiklopediya, M., 1977, 537 pp.