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


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


2. Покажем, что к задаче СУЩ полиномиально сводится задача ВЫП, которая является NP-полной. Пусть

- некоторая формула в базисе
. Рассмотрим формулу, реализующую функцию f
1 . Она, очевидно, принадлежит языку ВЫП, но ни одна переменная в такой формуле не является существенной. В формуле, реализующей функцию f
0, которая не принадлежит языку ВЫП, также нет существенных переменных. Все прочие формулы, принадлежат языку ВЫП, и хотя бы одна переменная в них является существенной. Таким образом, формула не принадлежит ВЫП, если её значение на любом битовом наборе (например, на наборе
) равно 0, и в ней нет существенных переменных. Таким образом, для проверки выполнимости формулы нужно проверить её значение в одной точке и m раз проверить существенность переменных формулы. Таким образом задача ВЫП полиномиально по Тьюрингу сводится к задаче СУЩ, что доказывает NP-полноту последней.

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

, пусть ? - множество всех таких функций, и пусть
- оракульная функция
:? - > {0,1} такая, что для любой функции f
?

(f)=0, если f
0,

(f)=1, в противном случае.

Обозначим через ?f формулу, реализующую функцию f. Пусть Ф - множество формул (потенциально бесконечное) такое, что если ?f - случайно и равновероятно выбранная формула из Ф, а f - функция, которую она реализует, то случайная величина

(f) принимает значение 1 с вероятностью p, а значение 0 с вероятностью q=1-p.

Множество формул Ф называется семейством непрозрачных предикатов, если для любого полиномиального вероятностного алгоритма A: Ф - > {0,1} выполняются условия

Теорема 2. Если непрозрачные предикаты существуют, то P

NP .

Доказательство. Пусть P = NP. Тогда существует полиномиальный алгоритм для решения задачи выполнимости, то есть существует алгоритм A, который для любой формулы ?f за полиномиальное проверит условие f

0 и выдаст ответ 0, если условие выполняется, и 1 в противном случае. Тогда P{A(?f)= 0|
(f)=0}=1, P{A(?f)= 0|
(f)}=1 , то есть непрозрачные предикаты не существуют. Полученное противоречие доказывает утверждение.




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



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