Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках | ПДМ. 2013. № 2(20).

Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках

В работе 1985 г. Дж. Лагариас и А. Одлыжко предложили метод решения вычислительной задачи о рюкзаке, основанный на её сведении к задаче поиска короткого вектора в решётке специального вида. Метод Лагариаса — Одлыжко позволяет решать «практически все» задачи о рюкзаках, обладающие малой плотностью. В настоящей работе метод Лагариаса — Одлыжко решения задачи о рюкзаке модифицируется применительно к случаям обобщённой задачи о рюкзаке и систем задач о рюкзаках. Система задач о рюкзаках вводится в настоящей работе как конечное множество индивидуальных задач о рюкзаках, имеющих общее решение. Определяются множества значений плотности обобщённых задач о рюкзаках и систем задач о рюкзаках, такие, что модифицированные методы позволяют решать «практически все» обобщённые задачи о рюкзаках и системы задач о рюкзаках, обладающие плотностью из этих множеств.

Modification of the Lagarias — Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems.pdf Введение Задача о рюкзаке (распознавания) NP-полна [1]. Однако на настоящий момент известны два метода решения вычислительных задач о рюкзаках, обладающих малой плотностью, один из которых предложен Дж. Лагариасом и А. Одлыжко [2], а второй— Э. Брикеллом [3]. Дж. Лагариас и А. Одлыжко рассматривали вычислительную задачу о рюкзаке в следующей формулировке. Условие: заданы вектор A = (a1, a2,..., ar) E Nr и число S E N, причём известно, что уравнение r = S, (1) i=1 где X1,... , xr — неизвестные, имеет решение в числах 0 и 1. Вопрос: найти решение уравнения (1) в числах 0 и 1. В работе [2] рассматривается понятие плотности задачи о рюкзаке. Определение 1. Плотностью задачи о рюкзаке с вектором A = (a1, a2,..., ar) E Nr называется число d -_r_ max a, log2 I max a, ) Метод Лагариаса — Одлыжко основан на сведении задачи о рюкзаке к задаче поиска короткого вектора в решётке специального вида. Предположим, что имеется алгоритм «Оракул», который за полиномиальное время выдаёт один из кратчайших (самых коротких) ненулевых векторов решёток некоторых специальных видов (виды решёток описаны далее). Несмотря на то, что задача нахождения кратчайшего ненулевого вектора решётки в общем случае является NP-трудной [4], ответ на вопрос 0 существовании алгоритма «Оракул» неизвестен, при реализации «приближением» к этому алгоритму служит алгоритм построения LLL-приведённого базиса решётки. Дж. Лагариас и А. Одлыжко рассматривали решётку Л1 = (zibi + ... + zr+ibr+i : zi,... , zr+i E Z}, образованную следующими линейно независимыми векторами размерности r + 1: bi = (1, 0,..., 0, N • ai), b2 = (0,1,..., 0, N • a2), br = (0, 0,..., 1, N • ar), br+i = (0, 0,..., 0, N • S), где N ^ [-^/r/2] + 1 —некоторое достаточно большое натуральное число, а вектор (ai,..., ar, S) E Nr+i задаёт вычислительную задачу о рюкзаке. В работе [2] показано, что справедлива следующая теорема. Теорема 1. Пусть ai,... , ar —произвольные натуральные числа, е = (ei,... , er) E r E (0,1}r — произвольный вектор и S = E e^a». Тогда вероятность ошибки при решении i=i задачи о рюкзаке, заданной значениями a», 1 ^ i ^ r, и S, при условии, что плотность этой задачи d3.p < 0,6463 ... , с помощью алгоритма «Оракул», применённого к решётке Л1, стремится к 0 при r ^ то. (Здесь и далее под ошибкой понимается получение с помощью «Оракула» вектора, отличного от е и —е.) Этот результат улучшен в работе [5] путём модификации исследуемой решётки. Определим решётку Л2 = (zibi + ... + zr+ib*+i : zi,... , zr+i E Z}, где b* = bj при 1 ^ i ^ r и b*+i = (1/2,1/2,..., 1/2, N • S), NV ^ [V^/2] + 1 — некоторое достаточно большое натуральное число. Заметим, что в данном случае векторы b*,...,b*+i не обязательно линейно независимы. Справедлива следующая теорема [5]. Теорема 2. Пусть ai,... , ar —произвольные натуральные числа, е = (ei,... , er) E r E (0,1}r — произвольный вектор и S = E e^a». Тогда вероятность ошибки при решении i=i задачи о рюкзаке, заданной значениями a», 1 ^ i ^ r, и S, при условии, что плотность этой задачи d3.p < 0,9408 ... , с помощью алгоритма «Оракул», применённого к решётке Л2, стремится к 0 при r ^ то. В настоящей работе предлагаются методы решения вычислительной обобщённой задачи о рюкзаке и систем задач о рюкзаках, основанные на методе Лагариаса — Од-лыжко решения вычислительной задачи о рюкзаке. Вычислительная обобщённая задача о рюкзаке рассматривается в следующей формулировке. Условие: заданы вектор A = (ai, a2,..., ar) E Nr, число S E N и натуральное число m ^ 2, причём известно, что уравнение r Е a^x» = S, (2) »=i где xi,...,xr — неизвестные, имеет решение в числах 0,1,..., m — 1. Вопрос: найти решение уравнения (2) в числах 0,1,... , m — 1. Замечание. Числа 0,1,... , m — 1 можно рассматривать как элементы кольца вычетов Z/mZ, но поскольку в обобщённой задаче о рюкзаке рассматривается обычная r сумма У] a*x натуральных чисел, то оперирование значениями 0,1,... ,m — 1 пред- *=1 ставляется более естественным. Определение 2. Плотностью обобщённой задачи о рюкзаке с вектором A = = (a1, a2,..., ar) G Nr назовём число d -_r_ "■о.з.р logm ^max ai) Системой задач о рюкзаках назовём конечное множество индивидуальных задач о рюкзаках, имеющих общее решение. Таким образом, система задач о рюкзаках является естественным обобщением индивидуальной задачи о рюкзаке. Кроме того, с точки зрения информационной безопасности система задач о рюкзаках тесно связана со случаем широковещательной рассылки сообщения, например в криптосистеме Меркля — Хеллмана. Дадим строгую формулировку системы обобщённых задач о рюкзаках. Условие: заданы k векторов A1 = (a11,..., ar1), ..., Ak = (a1k,..., ark) размерности r, k натуральных чисел S1,... , Sk и натуральное число m ^ 2, причём известно, что система уравнений r £ ajx* = Sj, 1 ^ j ^ k, (3) i=1 где X1,..., xr — неизвестные, имеет решение в числах 0,1,..., m — 1. Вопрос: найти решение системы уравнений (3) в числах 0,1,... , m — 1. Определение 3. Плотностью системы обобщённых задач о рюкзаках с векторами A1 = (a11,... ,ar1), ..., Ak = (a1k,..., ark) назовём число d =_r_ "-с.о.з.р / logTO ( max a Обозначим через Sr (Я) число точек целочисленной решётки, попавших внутрь или на поверхность r-мерной сферы радиуса л/Я с центром в начале координат (в r-мерном пространстве). В работе [2], по существу, доказана следующая теорема (непосредственно в работе рассматривался случай m = 2), необходимая нам для получения основных результатов. Теорема 3. Для всех a > 0, натуральных чисел r ^ 1 и любого натурального числа m ^ 2 Sr (ar) ^ eY = mY log™ e, те где y = min #(a,x) ■ r; #(a,x) = ax + ln0(e-x); 0(z) = 1 + 2 £ z* i=1 1. Модификация метода Лагариаса — Одлыжко для случая обобщённой задачи о рюкзаке Рассмотрим решётку Л3, образованную следующими векторами bi,... , br+i размерности r + 1 : bi = (1, 0,..., 0, N • ai), b2 = (0,1,..., 0, N • a2), br = (0, 0,..., 1, N • ar), br+i = (0, 0,..., 0, N • S), где N ^ [(m — 1)\/r/2] + 1 —некоторое достаточно большое натуральное число. Определение 4. Назовем обобщённую задачу о рюкзаке приведённой, если выполнены неравенства 1 r r 1 r - Е a» ^ S ^ (m — 1) Е a»--Е a». r »=i »=i r »=i Если обобщённая задача о рюкзаке не является приведённой, то имеется возмож- 1r ность исключить из рассмотрения либо самый большой (если - Е a» ^ S), либо самый r »=i r 1 r маленький (если S ^ (m — 1) Е a»--Е a») элемент вектора. Для приведённой обоб- »=i r »=i щённой задачи о рюкзаке такой возможности нет. Для любого натурального числа m ^ 2 справедлива следующая теорема. Теорема 4. Пусть ai,... , ar —произвольные натуральные числа, е = (ei,... , er) E r E (0,1,..., m — 1}r — произвольный вектор и S = E e^a». Тогда вероятность ошибки »=i при решении приведённой обобщённой задачи о рюкзаке, заданной значениями a», • ln m 1 ^ i ^ r, и S, при условии, что плотность этой задачи аозр < -—-—--, mm o((m — 1)2/2,x) с помощью алгоритма «Оракул», применённого к решетке Л3, стремится к 0 при r ^ то. Доказательство. Решётка Л3 содержит вектор e = (ei, e2,..., er, 0), где r ei,..., er —решение ассоциированной обобщённой задачи о рюкзаке (e = Е e^b» — br+i). »=i rr Пусть t = Е a». Можно считать, что Е e» ^ (m — 1)r/2, иначе можно перейти »=i »=i к «дополняющей» задаче со следующими параметрами: Snew = (m — 1)t — S, bn+w = (0,0,..., 0, N ((m — 1)t — S)), enew = (m — 1 — ei, m — 1 — e2,..., m — 1 — er, 0). Решение «дополняющей» задачи эквивалентно решению исходной задачи, при этом r E(m — 1 — e») ^ (m — 1)r/2 (заметим также, что Snew = (m — 1)t — S ^ (m — 1)t — »=i — (m — 1)t + t/r = t/r). Поскольку 53 e* ^ (m — 1)r/2, e* G {0,1,..., m — 1} и h2 + (m — 1 — h)2 ^ (m — 1)2 i=1 при 0 ^ h ^ m — 1, то ||e||2 = £ e- ^ (m — 1)2r/2. i=1 Поэтому вектор e является «достаточно коротким» вектором решётки и его можно искать при помощи «Оракула». Однако может оказаться, что «Оракул» выдаст вектор, не совпадающий с векторами — e, e. В этом случае вектор, предоставленный «Оракулом», является элементом следующего множества ошибочных векторов: X3 = {x = (X1,... ,Xr+1) : X G Лз, ||x|| ^ ||e||,x G {—e, 0,e}}. Выбор числа N ^ [(m — 1)\Jr/2] +1 обеспечивает для векторов x G X3 выполнение условия xr+1 = 0 (иначе если x G X3 и xr+1 = 0, то ||x|| ^ |xr+1| ^ N > (m — 1)^/r/2 ^ ^ ||e||, то есть x G X3 — противоречие). Рассмотрим произвольный вектор x G X3 и определим число y G Z следующим образом: r yS = xiai, i=1 тогда r ^ ||x|| E a* ^ (m — 1)tyr/2 i=1 и, поскольку t ^ Sr, получим |y| ^ (m — 1)r^/r/2. Пусть P — вероятность того, что множество X3 не является пустым, тогда справедливо неравенство P ^ P^53 x*a* = yS | x G X3, |y| ^ (m — 1)г^г/2^ У : |y| ^ (m — ^rv^} Определим вектор z = (z1, z2,... , zr), где z* = x* — ye*, 1 ^ i ^ r. Случай z = 0 не рассматривается, поскольку при этом ||x|| = |y|||e||, и так как ||x|| ^ ||e||, то |y| ^ 1 и x G {—e, 0, e}, а значит, x G Х3. Пусть B = max a*, без ограничения общности будем считать, что z1 = 0. Определим a*z* z = — Е —, *=2 z1 тогда Pr ( Е z*a* = 0) = Pr(a1 = z*) = E Pr(a1 = z* | z* = j)Pr(z* = j) = \*=1 / j=1 B B 1 1 = E Pr(a1 = j)Pr(z* = j) = E -Pr(z* = j) ^ -. j=1 j=1B B |y|S = 53 x*a* i=1 Предыдущая оценка получена в предположении, что z1 = 0, но на самом деле каждый элемент z* при 1 ^ i ^ r может быть не равным нулю, поэтому Pr (33 z*a* = 0^ ^ С учётом результата теоремы 3 при а = (m — 1)2/2 получим min5((m-1)2/2,ж)г logm e |Хз| ^ |X E Zr : ||X|| ^ (m — 1)Vr/2 По свойствам модуля |y : |y| ^ (m — 1)r^r/2 j ^ 2(m — 1)гУг/2 + 1 Таким образом, min 5((m-1)2/2,ж)г logm e P ^ r ^2(m — 1)r Vr/2 + 1) m B если B = mCmr, то при Cm > min$((m — 1)2/2,x)logm e получим lim P = 0. и r r Если плотность обобщённой задачи о рюкзаке ln m min $((m — 1)2/2, x)' ж>0 < о.з.р logm ( max a, min 5((m-1)2/2,ж)г logm e то B = max a» > . ■ i^r 2. Модификация метода Лагариаса — Одлыжко для случая систем обобщённых задач о рюкзаках Рассмотрим решётку Л4, образованную следующими векторами b1,... , br+1 размерности r + k: b1 = (1, 0,..., 0, N • a11, N • a12,..., N • a1k), b2 = (0,1,..., 0, N • a2i, N • a22,..., N • a2fc), br = (0, 0,..., 1, N • ar1, N • ar2,..., N • ark), br+i = (0, 0,..., 0, N • Si, N • S2,..., N • Sfc), где N ^ [(m — 1)\/r/2] + 1 —некоторое достаточно большое натуральное число. Определение 5. Назовём систему обобщённых задач о рюкзаках приведённой, если для всех 1 ^ j ^ k выполнены неравенства 1 r r 1 r - Е aj ^ Sj ^ (m — 1) Е ajj--Е a^. r г=1 г=1 r г=1 Для любого натурального числа m ^ 2 справедлива следующая теорема. Теорема 5. Пусть a^, 1 ^ i ^ r, 1 ^ j ^ k, — произвольные натуральные числа, причём векторы A1 = (a11,... , ar1), ... , A^ = (a1^,... , ar&) являются линейно независиr мыми. Пусть е = (e1,... , er) E (0,1,... , m — 1}r —произвольный вектор и Sj = Е e^ay г=1 для всех 1 ^ j ^ k. Тогда вероятность ошибки при решении приведённой системы обобщённых задач о рюкзаках, заданной значениями a^, 1 ^ i ^ r, 1 ^ j ^ k, и Sj, k ln m 1 ^ j ^ k, при условии, что плотность этой системы ас о з р < -—-—--, с поmin o((m — 1)2/2,x) мощью алгоритма «Оракул», применённого к решётке Л4, стремится к 0 при r ^ то. Доказательство. Решётке Л4 принадлежит вектор e = (e1,..., er, 0,..., 0), где e1,... , er —решение ассоциированной системы обобщённых задач о рюкзаках. Отметим, что, как и ранее, можно считать, что ||e||2 ^ (m — 1)2r/2. Множеством ошибочных векторов в этом случае является X4 = {x = (x1,... ,xr+1) : x G Л4, ||x|| ^ ||e||,x G {—e, 0, e}}. (m — 1^v/r72 +1 обеспечивает выполнение для векторов x G X4 условия xr+j = 0 для всех 1 ^ j ^ k (иначе если x G X4 и xr+j- = 0 для некоторого 1 ^ j ^ k, то ||x|| ^ |xr+j| ^ N > (m — 1)^/r/2 ^ ||e||, то есть x G X4 —противоречие). r Пусть tj = E a'j для всех 1 ^ j ^ k. Рассмотрим произвольный вектор x G X4 и i=1 определим число y G Z следующим образом: Выбор числа N ^ ySj = 53 x'a'j для всех 1 ^ j ^ k, i=1 ^ ||x|| E aij ^ (m — 1)tj/Д i=1 xiaij i=1 тогда для всех 1 ^ j ^ k |y|Sj и поскольку tj ^ Sj r, получим |y| ^ (m — 1)^v/r72; более точную оценку может дать неравенство |y| ^ (m — 1) mm {tj/Sj} л/Т/2. Пусть P — вероятность того, что множество X4 не является пустым, тогда справедливо неравенство / r r _\ P ^ Pr Е xiai1 = ySb..., Exiaifc = ySk | x G X4, |y| ^ (m — ■ \i=1 i=1 J x|{y : |y| ^ (m — 1)r/r72}| = П Pr ( E xiaij = ySj | x G X4, |y| ^ (m — 1)r/r72J x j=1 \i=1 J x|X4| ■ |{y : |y| ^ (m — 1)r/r/2}|. Пусть B = max aj. Как и прежде, можно показать, что для всех 1 ^ j ^ k pW £xiaij = ysj j ^ в jy : |y| ^ (m — 1)r/r7^} ^ 2(m — 1)r/r/2 + 1, _imin S ((^^_1)2 /2 x X ^ |{x G Zr : ||x|| ^ (m — 1^л/г72}| ^ m^0 (( ) 7 , Таким образом, в этом случае minS((m-1)2/2,x)r logm e B k mx / - \ P ^ rk (2(m — 1)r\Jrf2 + 1J и если B = mCmr/fc, то при Cm > min $((m — 1)2/2,x) logm e получим lim P = 0. Если плотность системы обобщённых задач о рюкзаках r k ln m dc .о . з .p 7 \ < с " . 3 р п / \ ^ min £((m — 1)2/2,x) logm max «j 1 10 ( ' , ' g2 . Численно устанавливается, что min $(1/4, x) log2 e = 1,0628 ... Следовательно, можно утверждать, что |{x : ||x|| ^ VT/2}| ^ 2Cir + 2r, где C1 = 1,0628... Пусть B = max ai7-. Как и прежде, можно показать, что для всех 1 ^ j ^ k кп г- . ^2Cir + 2r Pr ^£ x^- = 2y(tj — 2Sj^ ^ B_, |{y : |y| ^ 2rVT}| ^ + 1. Таким образом, в этом случае P ^ rk(4г^ + 1): Bk ' и если B = 2Cr/k, то при C > C1 получим, что lim P = 0. Если плотность системы задачи о рюкзаках r dc.3.p =-у-- < k ■ 0,9408 ..., log2 I max ai7то B = max ai?- > 2Cir/k. ■

Ключевые слова

метод Лагариаса — Одлыжко, задача о рюкзаке, обобщённая задача о рюкзаке, системы задач о рюкзаках, Lagarias — Odlyzhko method, knapsack problem, generalized knapsack problem, systems of knapsack problems

Авторы

ФИООрганизацияДополнительноE-mail
Мурин Дмитрий МихайловичЯрославский государственный университет им. П. Г. Демидовааспирантnirum87@mail.ru
Всего: 1

Ссылки

Karp R. M. Reducibility among combinatorial problems // Complexity of Computer Computations. Plenum Press, 1972. P. 85-103.
Odlyzko A.M. and Lagarias J. C. Solving low-density subset sum problems // J. Association for Computing Machinery. 1985. V.32. No. 1. P. 229-246.
Brickell E. F. Solving low-density knapsacks // Advances in Cryptology. Proc. Crypto'83. Plenun Press, 1984. P. 25-37.
Boas P. Another NP-complete problem and the complexity of computing short vectors in a lattice // Tech. rep. 8104, University of Amsterdam, Department of Mathematics, Netherlands, 1981. 10 p.
Coster M. J., Joux A., LaMacchia B. A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. No. 2. P. 111-128.
 Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках | ПДМ. 2013. № 2(20).

Модификация метода Лагариаса — Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках | ПДМ. 2013. № 2(20).

Полнотекстовая версия