LLL-решатель

В работе обсуждается подход к решению за «приемлемое время» представителей NP-полных Задач — LLL-решатель. Подход основан на методе решения Задачи о рюкзаке, предложенном Лагариасом и Одлыжко. Доказано существование полиномиальной трансформации Задачи 3-ВЫП в Задачу о рюкзаке, при которой образ Задачи 3-ВЫП попадает в область задач о рюкзаке с плотностью $d<C$, где $C$ — любая заданная константа, не превосходящая $3(\log_27)^{-1}$. Предложено понятие функции применимости алгоритма к решаемой задаче, приведены результаты компьютерных экспериментов по вычислению функций применимости LLL-решателя к решению задач о рюкзаке.