Использование радиуса устойчивости оптимизационных задач для скрытия и проверки …
5
Далее, для сокрытия информации отправитель использует все
элементы
А
, кроме элементов оптимальной траектории. При этом
можно использовать не сами элементы, а их веса.
Затем отправитель увеличивает веса всех элементов кроме весов
элементов оптимальной траектории, например, на величину, равную
половине радиуса устойчивости. И эта новая «возмущенная» матрица
А
′ отправляется получателю.
Получатель для восстановления информации должен просто ре-
шить задачу и найти радиус устойчивости. После этого он вычитает
его значение из всех элементов матрицы, кроме элементов оптималь-
ной траектории. Таким образом восстанавливается исходная (невоз-
мущенная) матрица.
Злоумышленник, зная тип и размерность задачи, не сможет вос-
становить информацию без знания процедуры применения радиуса
устойчивости.
Заключение.
Первая из предложенных методик основана на не-
возможности эффективного решения
NP
-трудной задачи. Вторая же,
наоборот, предполагает решение полиномиально разрешимой задачи,
однако требует и наличия эффективного алгоритма поиска радиуса
устойчивости.
Как правило, для полиномиально разрешимых задач и радиус
устойчивости находится за полиномиальное время, хотя степень по-
линома, характеризующего трудоемкость его вычисления, может
быть выше, чем степень аналогичного полинома для алгоритма ре-
шения самой задачи.
Задачи на матроидах и пересечении матроидов сами решаются с
полиномиальной сложностью и алгоритмы нахождения радиуса
устойчивости тоже полиномиальны. (Сюда входит задача о кратчай-
шем остове. Задача о назначениях и многие другие известные опти-
мизационные задачи).
Для некоторых потоковых задач и частных случаев задачи о крат-
чайшем пути также существуют полиномиальные алгоритмы нахож-
дения радиуса устойчивости. Однако, в общем случае, с точки зрения
исследования устойчивости, задача о кратчайшем пути требует на се-
годня экспоненциального алгоритма [7]. Так как в данном случае
наличие циклов отрицательной длины не может быть исключено.
ЛИТЕРАТУРА
[1]
Sotskov Yu.N., Leontev V.K., Gordeev E.N.Some concepts of stability
analysis in combinatorial optimization.
Discrete Applied Mathematics,
1995,
vol. 58, pp. 169–190.
[2]
Гордеев Э.Н., Леонтьев В.К. Общий подход к исследованию устойчивости
решений в задачах дискретной оптимизации.
Журнал выч. мат. и мат.
физ
., 1996, т. 36, с. 66–72.
