Об одном методе маскировки программ


Теоретическое обоснование устойчивости метода


Настоящий раздел посвящён анализу устойчивости предложенного метода маскировки.

Предварительно дадим некоторые вспомогательные определения и теоремы. Пусть

. Пусть poly(n) - произвольный многочлен от переменной n.

Определение 1. Пусть

, пусть m=poly(n). f называется односторонней функцией, если для любого полиномиального вероятностного алгоритма A и для любого
выполняется соотношение
.

Определение 2. Взаимно-однозначная односторонняя функция

называется односторонней перестановкой.

Определение 3. p-приближённым алгоритмом решения оптимизационной задачи называется алгоритм, находящий решение не более чем в p раз хуже оптимального решения.

Например рассмотрим задачу S минимизации некоторого функционала f. Пусть A - p -приближённый алгоритм нахождения решения задачи S. Пусть для некоторой реализации задачи оптимальное значение функционала равно X. Тогда алгоритм A найдёт решение задачи, при котором значение f равно Y, причём будет справедливо неравенство

.

Определение 4. Пусть

. Пусть x=(x1....,xm), y=(y1....,yn), y=f(x). Переменная xk называется существенной, если существуют x1,...,kk-1,xk+1,...,xm
и j
{1,...,n} такие, что выполняется условие fj(x1,...,xk-1,0,xk+1,...,xm
fj(x1,...,xk-1,1,xk+1,...,xm ).

Теорема 1. Пусть

, f записана как система булевских формул в базисе
. Пусть
. Задача проверки существенности переменной xk (СУЩ) NP-полна.

Доказательство. Введём обозначение

, где e1 e2 , - булевские формулы. Обозначим
,
,
.

1. Покажем, что задача СУЩ находится в классе NP. Для этого построим булевскую формулу

.

Если переменная существенна, то существует такой вектор

, для которого g(
)=1. Если переменная несущественна, то на всех наборах
выполняется g(
)=0. И наоборот, если g(
) принадлежит языку ВЫП, то переменная xk существенна, а если g(
) не принадлежит языку ВЫП, то xx - несущественна. Таким образом, задача проверки существенности сведена к задаче проверки выполнимости булевской формулы. Последняя находится в классе NP. Следовательно, и задача проверки существенности находится в классе NP.




Начало  Назад  Вперед



Книжный магазин