О coNP-полноте задачи «Инъективный рюкзак» | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/7

О coNP-полноте задачи «Инъективный рюкзак»

Устанавливается coNP-полнота задачи «Инъективный рюкзак».

About the coNP- complete "Injective knapsack" problem.pdf 1. Задачи о рюкзаках Хорошо известно [1 -3], что «Проблема рюкзака», или «Проблема суммы элементов подмножеств», является NP-полной. Она может быть сформулирована как вопрос о разрешимости в числах 0, 1 уравнения вида (1) a1^1 + ... + anXn = b где a1, ..., an и b - произвольные натуральные числа; x1, ..., xn - неизвестные. В 1978 г. Р. Меркль и М. Хеллман [4] предложили первую (в открытых источниках) асимметричную систему шифрования, которая базировалась на «Проблеме рюкзака». Спустя четыре года А. Шамир показал, что метод генерации открытых ключей по закрытым в криптосистеме Меркля - Хеллмана не является надёжным и практически все индивидуальные представители «Проблемы рюкзака», возникающие при использовании этой системы, поддаются решению. Несмотря на результаты А. Шамира, «Проблема рюкзака» обладает полезными для криптографии свойствами: во-первых, о ней известно, что она является достаточно сложной, и, во-вторых, процесс шифрования в криптосистеме Меркля - Хеллмана существенно быстрее, чем процесс шифрования в криптосистеме RSA, и представляется вероятным, что можно построить стойкие криптосистемы, основанные на «Проблеме рюкзака», с высокой скоростью шифрования и расшифрования, что является крайне важным прикладным свойством, например для задачи синхронизации центров обработки данных по неконтролируемому (незащищённому) каналу связи. Благодаря этим свойствам работы по созданию криптосистем, базирующихся на «Проблеме рюкзака», не прекращаются [5-8]. В работе [7] введена в рассмотрение «Проблема обобщённого рюкзака», которая для фиксированного натурального числа m ^ 2 состоит в ответе на вопрос, разрешимо ли уравнение (1) в числах 0,1,..., m - 1. В связи с шифрсистемой с открытым ключом, предложенной Р. Мерклем и М. Хелманом на основе «супервозрастающего» рюкзака, стали представлять особый интерес так называемые «Инъективные рюкзаки». Будем говорить, что набор различных натуральных чисел а1, ... , an определяет «Инъективный рюкзак» (соответственно «m-инъективный рюкзак»), если не существует двух различных наборов чисел 0, 1 (соответственно наборов чисел 0, ..., m - 1, где натуральное число m ^ 2) а1, ... , an и в1, ... , вп, таких, что a1«1 + ... + an^n = a1^1 + ... + апвп. В противном случае набор натуральных чисел а1, ..., an определяет «Неинъективный рюкзак» (соответственно «m-неинъективный рюкзак»). Задача «Инъективный рюкзак» Дано: набор различных натуральных чисел a1, ... , an. Определить: является ли определяемый ими рюкзак инъективным. Задача «Неинъективный рюкзак» Дано: набор различных натуральных чисел a1, ... , an. Определить: является ли определяемый ими рюкзак неинъективным. Задача «m-инъективный рюкзак» Дано: набор различных натуральных чисел a1, ... , an, натуральное число m ^ 2. Определить: является ли определяемый числами a1, ... , an рюкзак m-инъективным. Задача «m-неинъективный рюкзак» Дано: набор различных натуральных чисел a1, ... , an, натуральное число m ^ 2. Определить: является ли определяемый числами a1, ... , an рюкзак m-неинъективным. Очевидно, что задача «2-инъективный рюкзак» эквивалентна задаче «Инъективный рюкзак», поэтому задача «m-инъективный рюкзак» включает в себя задачу «Инъ-ективный рюкзак». Ясно, что задача «Неинъективный рюкзак» является дополнением задачи «Инъективный рюкзак» и принадлежит классу NP. Аналогично задача «m-неинъективный рюкзак» является дополнением задачи «m-инъективный рюкзак» и, в силу включения задачи «Неинъективный рюкзак», принадлежит классу NP. 2. Теорема о coNP-полноте задачи «Инъективный рюкзак» Теорема 1. Задача «Инъективный рюкзак» является coNP-полной. Доказательство. Необходимо доказать, что задача «Неинъективный рюкзак» (дополнение задачи «Инъективный рюкзак») является NP-полной. Так как она принадлежит классу NP, то остаётся доказать её NP-трудность. Для этого достаточно установить полиномиальную сводимость к ней некоторой подходящей NP-полной задачи. В качестве таковой возьмём задачу о разрешимости в числах 0, 1 уравнения вида n 2(a1X1 + ... + anXn)^J2 ai, (2) i=1 где а1, ..., ап - произвольные натуральные числа. Эта задача хорошо известна под названием «Разбиение». Столь же хорошо известна и её NP-полнота. При построении полиномиальной сводимости воспользуемся некоторыми идеями работы [9], c которой нас любезно познакомил М. В. Волков. По коэффициентам уравнения (2) по аналогии с работой [9] построим последовательность из 3n натуральных чисел , On, bl, ... ,bn, Ci,.. . ,Cn, (3) ai, полагая a = Oi ■ 102n + 10n+i-i + 10i-i для i = 1,..., n, Ьг = 10n+i-i + 10i для i = 1,... ,n - 1, bn = 102n-i + 1, ci = 2 ■ 10i-i для i = 1,..., n. Покажем, что уравнение (2) имеет решение в числах 0, 1 тогда и только тогда, когда натуральные числа (3) образуют «Неинъективный рюкзак». Рассмотрим функцию f ( xi,..., Xn, yi,..., Уп, zi,..., Zn) = aiXi + ... + anXn + biyi + ... + ЬпУп + CiZi + ... + CnZ„ Для произвольных десятичных цифр di, ..., dk через dk ... dil0, как обычно, будем обозначать число 4 ■ 10k-i + ... + d2 ■ 10 + di. Рассмотрим f как отображение множества {0,1}3п в множество натуральных чисел. Тогда натуральные числа (3) задают «Неинъективный рюкзак» в том и только в том случае, когда это отображение не является инъективным. Нетрудно понять, что для произвольных чисел ai, ..., an, въ ... , вп, 7ъ ..., Yn из множества {0,1} справедливо равенство f ( ai,... ,«п,въ ... ,вп, Yi,..., Yn)=( aiai + ... + Onan)102n+( вп + an) ... ( ei + ai)i0-10n+ i0 + ( en-i + an + 2Yn)( en-2 + an-i + 2Yn-i)... (ei + «2 + 2Y2)( en + ai + 2yi) Поэтому для произвольных чисел ai, ..., an, въ en, Yi, ..., Yn из множества {0,1} равенство f ( ai,... ,an ,ei,... ,en,Yi,..., Yn) = f ( ai, равносильно системе равенств ai ai + ... + anan = aia'i + . en + an + an, en -i + an-i = en- i + an-1, ., en, Yi, .. ,an,e'i, + Onan, Yn, «i, > Дп , Yi , . . . , Yn) e2 + a2 = e2 + a2, ei + ai = ei + ai, en-i + an + 2Yn = en-i + an + 2Yn, en-2 + an-i + 2Yn-i = en-2 + an. i + 2тП_ i ei + a2 + 2Y2 = ei + a'2 + 2y2 , lA + ai + 2yi = en + ai + 2y1 . Предположим, что уравнение (2) имеет решение ai, ..., an в числах 0, 1. Покажем, что найдутся такие числа въ ..., вп, 7i,..., In, ai,..., аП, ,..., вП, 7i,..., 7п ^ {0,1}, которые нарушают инъективность рюкзака (3), т.е. наборы (ai,..., an, въ ..., вп, 7i,..., 7п) и (а1,...,аП , в1, . . . , вп, 71, . . . , In) различны, но выполняется равенство /(а i,...,an,ei,...,en,7i,...,7n) = / (ai ,...,a'n,e 1 ,...,e'n ,71 ,...,7n). Уравнение (2) даёт равенство a ia i + ... + anan = ai(1 - a i) + ... + an(1 - an), поэтому в качестве чисел a', ..., an можно взять 1 - a i, ... , 1 - an. Тогда ai = a'i при произвольном i, 1 ^ i ^ n. Для нахождения чисел ei, ..., вп,, 7i, ..., 7n, в1, ..., в'п, 7l, Yn получаем две системы вп + 2an = 1 + вп, вп- i + 2 an- i = 1 + в'п-1, в2 + 2a2 = 1+ в2, в i + 2a i = 1 + в' и вп- i + 2an = 1 + вп- i + 2(Yn - 7n), вп-2 + 2an- i = 1 + вп-2 + 2(7n- i - 7n-i), вl + 2a2 = 1 + в' + 2(72 - 72), вп + 2a i = 1+ вп + 2(y i - 7l). Из первой системы при произвольном i, 1 ^ i ^ n, получаем вi - в'' = 1 - 2ai. Правая часть этого равенства равна ±1, что позволяет при любом значении a' однозначно определить числа в' и в'. При этом в' - в' = ±1, поэтому в' + в' = 1. Для нахождения чисел Yi, ... , Yn, 7', ... , 7^ воспользуемся системой вп- i + 2an = 1 + вп- i + 2(7п - 7п), вп-2 + 2an- i = 1 + вп-2 + 2(7п- i - 7п-i), в + 2a2 = 1+ в1 + 2(72 - 72), _вп + 2a i = 1+ вп + 2(7i - 7l). При 2 ^ i ^ n получаем равенство 2(7' - 7') = 2a' - (1 + (в'- i, -в'-i)). Так как в' + в' = 1, то 7' - 7' = a' - 1 + в'- i. Это уравнение разрешимо при любых a' и в'- i. Для нахождения 7i и 7' воспользуемся уравнением 7' - 7i = a i - 1 + вп. Для доказательства обратного предположим, что для двух различных наборов (a i,... ^п,въ ... ,вп,7ь ... ,7п) и (a',..., an ,в', ...,вп ,7', ...,7п) чисел 0, 1 выполняется равенство /(a i,... ,an,вi,...,вп,7i, • Это даёт равенство a ia i + ... anan вп + an вп + an, вп - i + an- i = i + an- i , ,7n) = /(ai ,...,an ,в' ,...,вп,7' ,...,VJ. -a ia/i + ... ana^ и две системы равенств вп- i + an + 27п = вп- i + an + 27п, вп-2 + an-i + 27п- i = вп-2 + an- i + 27n- i, и в2 + a2 = в2 + a2, в i + a i = в' + a' в i + a2 + 272, вп + a' + 27', в i + a2 + 272 вп + a i + 27i которыми воспользуемся для доказательства равенств al = 1 - а1, Перепишем эти системы в более наглядном виде: . . . , - 1 вп вп an an, вп-1 вп- 1 an- 1 an-Ъ в2 - в2 = а2 - «2, в1 - в1 = a; - а1 и (вп-1 - вП-i) + (an - aW) + 2(Yn - yW ) = 0, (в„_2 - вП-2) + (an-1 - aW-1) + 2(Yn-1 - YW-1) = 0, (в; - в!) + (a2 - a2) + 2(72 - y2 ) = 0, (вп - вП) + (a1 - a;) + 2(y1 - Y'I ) = 0. Предположим, что при некотором i выполняется равенство a^ двигаясь по системам вверх, последовательно получаем 1) в = в', (ai+i - ai+i) + 2(Yi+i - Yi+i) = 0 2) 3) 4) 5) 6) (ai+i a i+1 ) и (Yi+i = Yi+iX A+l = ei+1, (ai+2 - ai+2) + 2(Yi+2 - Yi+2) (ai+2 = ai+2) и (Yi+2 0, 0, 3(n - i)) (an = aW) и (Yn = YW)> 3(n - i) + 1) вп = вп, 3(n - i) + 2) (a; - al) + 2(yi - Yl) 3(n - i) + 3) (a; = al) и (yi = y'i). Продолжая двигаться по системам вверх, получим, что наборы a'. Если i < n, то, >в1 ,...,вП ,Y! ,...,YW ) (ai, ,в1,... ,вп, Yl,..., Yn) a a и совпадают, что противоречит предположению. Значит, при любом i выполняется равенство ai = 1 - a^. Поэтому набор (a;,..., an) является решением уравнения (2). Это завершает доказательство теоремы. ■ Следствие 1. Задача «m-инъективный рюкзак» является coNP-полной. Заключение В работе доказано, что задача «Неинъективный рюкзак» является NP-полной, а задача «Инъективный рюкзак» - coNP-полной. При этом интересно отметить, что с определённой точки зрения «Инъективных рюкзаков» практически столько же, сколько «Неинъективных». В работах [10, 11] устанавливается, что число «Инъективных рюкзаков» размерности n с фиксированным максимальным элементом M ограничено снизу величиной ■M - 2п-1 + 1 M- 2п-1 + 1 \п-2 п1 где полагаем M ^ 2 Ш| -;----1 п1 2 2 п2 а сверху - ^(J-1;, где полагаем M ^ n; ( -число сочетаний. Отметим, что оценки эти достаточно грубые, поскольку нижняя оценка получена фактически для «Супер-возрастающих рюкзаков», а если рассмотреть верхнюю оценку для числа «Инъектив-ных рюкзаков», максимальный элемент которых принимает значения от n до M, то получим . M = , 1+ n , (n + 1)n , (n + 2)(n + 1)n + , (M - 1) ... (n + 1)n ^kk4- = n vol + H + 2! + 3! +... + (M-n)! _ / (n + 2)(n +1) (n + 2)(n + 1)n (M - 1)... (n + 1)n n\ 2! + 3! +... + (M - n)\ .M (M - 1)... (n + 1) M! n! (M - n)\ (M - n)!: M! и поскольку lim j-^-yj\/[n = 1, то «практически все» рюкзаки должны быть инъективными. Действуя по аналогии, можно установить, что число «m-инъективных рюкзаков» размерности n с фиксированным максимальным элементом M ограничено снизу величиной M - mn-1 + 1 л/ M - mn-1 + 1 \ n-2 _ n_ 1 n! ( --г--- 1) (---) , где полагаем M ^ m V (m - 1)mn-2 / V mn-1 J а сверху - n!Cn-1, где полагаем M ^ n(m - 1); k = [(M - m + 1)/(m - 1)]. Если посмотреть на все оценки, как на полиномы от M, то окажется, что каждый полином имеет степень n - 1. При этом общее число «рюкзаков» размерности n с фикn сированным максимальным элементом M составляет Mn - (M - 1)n = Ck(M - 1)n-k k=1 и также является полиномом степени n - 1 от M. Это означает, что доля «Инъектив-ных рюкзаков» размерности n среди всех рюкзаков зависит только от n, то есть при фиксированном n эта доля является константой, соответственно является константой и доля «Неинъективных рюкзаков».

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

NP-полные и coNP-полные задачи, инъективный 'рюкзак, т-инъективный рюкзак, NP-complete and coNP-complete problems, injective knapsack, m-injec-tive knapsack

Авторы

ФИООрганизацияДополнительноE-mail
Дурнев Валерий ГеоргиевичЯрославский государственный университет им. П. Г. Демидовапрофессор, доктор физико-математических наук, заведующий кафедрой компьютерной безопасности и математических методов обработки информацииdurnev@uniyar.ac.ru
Зеткина Оксана ВалерьевнаЯрославский государственный университет им. П. Г. Демидовадоцент, кандидат экономических наук, доцент кафедры мировой экономики и статистикиoks_68@mail.ru
Зеткина Алена ИгоревнаЯрославский государственный университет им. П. Г. Демидовамагистрантка кафедры мировой экономики и статистикиaizetkina@gmail.ru
Мурин Дмитрий МихайловичЯрославский государственный университет им. П. Г. Демидовакандидат физико-математических наук, старший преподаватель кафедры компьютерной безопасности и математических методов обработки информацииnirum87@mail.ru
Всего: 4

Ссылки

Karp R.M. Reducibility among combinatorial problems // Complexity of Computer Computations. N.Y.: Plenum Press, 1972. P. 85-103.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984.
Merkle R. and Hellman M. Hiding information and signature in trapdoor knapsacks // IEEE Trans. Inform. Theory. 1978. V. 24. No. 5. P. 525-530.
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problems Control Inform. Theory. 1986. No. 15(2). P. 159-166.
Chor B. and Rivest R. A knapsack-type public key cryptosystem based on arithmetic in finite fields // CRYPTO'84. LNCS. 1985. V. 196. P. 54-65.
Осипян В. О. О криптосистемах с заданным рюкзаком // Материалы VI Междунар. науч.-практич. конф. «Информационная безопасность». Таганрог: Изд-во ТРТУ, 2004. С.269-271.
Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета. 2006. Т. 309. №2. С. 209-212.
Woeginger G. J. and Yu Z. On the equal-subset-sum problem // Inform. Proc. Lett. 1992. V. 42. P. 299-302.
Мурин Д. М. О порядке роста числа инъективных и сверхрастущих рюкзачных векторов // Моделирование и анализ информационных систем. 2012. Т. 19. №3. С. 124-135.
Мурин Д. М. О порядке роста числа инъективных и сверхрастущих векторов и некоторых особенностях сильного модульного умножения // Прикладная дискретная математика. Приложение. 2012. №5. С. 19-21.
 О coNP-полноте задачи «Инъективный рюкзак» | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/7

О coNP-полноте задачи «Инъективный рюкзак» | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/7