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


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


Если переменная xk несущественная для f, то все переменные xk,z1,...,zm-1 несущественны для f1. С другой стороны, если хотя бы одна переменная из множества {xk,z1,...,zm-1} окажется несущественной в f1, то и все переменные этого множества будут несущественными.

В таком случае пусть p=m-1 . Тогда, если задача ЗАВ для функции f1 , множества переменных I и значения p даёт ответ "да", отсюда следует, что все переменные xk,z1,...,zm-1 несущественны, а если ответ "нет", то все эти переменные существенны.

Таким образом задача СУЩМНОЖ сводится к задаче ЗАВ, что показывает NP-полноту последней.

Рассмотрим оптимизационную задачу ЗАВ. Она состоит в нахождении такого Win

Vin , что p=|Win| минимально. Из NP-полноты задачи проверки свойств следует NP-трудность оптимизационной задачи.

Теорема 7. Если P

NP, то для любого p>1 не существует полиномиального p-приближённого алгоритма решения оптимизационной задачи ЗАВ

Доказательство. Пусть существует такое p>1 , что существует полиномиально-ограниченный алгоритм A, который находит множество существенных переменных WinA такое, что pA=|WinA|

P*p
n , где p - оптимальное решение. Очевидно, 0
p
pA
P*p
n.

Рассмотрим следующую реализацию задачи СУЩ. Пусть f - булевская функция f:

m - >
n. Предположим для определённости, что f записана в виде КНФ. Для определённости будем считать, что x1=v1,...,xm=vm - переменные, используемые при вычислении функции, а y1=vm+1,...,yn=vm+n - переменные, получающие своё значение. Пусть требуется проверить существенность переменной xk относительно множества I.

Пусть [x] - минимальное целое число, не меньшее x. Введём l=m*[p] новую переменную z1,...,zl следующим образом: каждое вхождение xk в формулу для вычисления f заменим на выражение xk v z1 v ... v zl , а выражение

k - на выражение
. В результате получим функцию f1 :
m+1 - >
n , которая также записана в КНФ.

Обозначим через Win0 оптимальное решение оптимизационной задачи ЗАВ для формулы f, а через Win1 - оптимальное решение для формулы f1 .


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



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