Однако если элементы из правой части равенства (7) необрати-
мы, то достаточно сложно создать алгоритм, который автоматически
генерировал бы
ν
0
. . . ν
n
таким образом, чтобы они, удовлетворяя ра-
венству (7), не сводились к системе (8).
Итак, из всего сказанного ранее можно сделать вывод, что при авто-
матической генерации подпрограмм с функциональными свойствами
ν
0
. . . ν
n
мы не можем гарантированно утверждать, что не существу-
ет эффективного алгоритма оптимизации, позволяющего восстановить
исходную последовательность (5).
Предположим теперь, что
π
=
π
0
∗
ν
0
∗
π
1
∗
ν
1
∗
π
2
∗
ν
2
∗
. . .
∗
π
n
∗
ν
n
=
π
исх
,
(13)
т.е. подпрограмма
O
(
M
)
обладает функциональным свойством, отлич-
ным от функционального свойства подпрограммы
M
. Этого можно
добиться посредством введения глобального по отношению к под-
программе
O
(
M
)
контекста. Если подпрограммы с функциональными
свойствами
ν
0
. . . ν
n
будут работать с фальшивым контекстом, сохра-
няя в нем результат, то достаточно сложно будет отделить истинные
данные от ложных, не анализируя при этом подпрограмму
A
. Оче-
видно, что несводимость равенства (7) к системе (8) тоже достаточ-
но легко обеспечить. Для достижения желаемого злоумышленником
эффекта алгоритмы оптимизации нужно будет теперь применять по
отношению к подпрограммам
A
и
O
(
M
)
.
Теорема.
Задача определения существенности функционального
свойства
π
i
(
ν
i
)
в равенстве (13)
NP
-полна.
Доказательство.
Докажем сначала сводимость задачи определе-
ния существенности функционального свойства к задаче выполнимо-
сти булевой формулы. Для того чтобы проверить существенность неко-
торого функционального свойства (т.е. влияние его наличия на резуль-
тат работы программы), необходимо исключить это функциональное
свойство из последовательности (13) и проверить результаты выполне-
ния подпрограммы на всех входных наборах, т.е., по сути, выполнить
булеву формулу следующего вида:
i
(
X
i
·
Y
i
)
,
(14)
где
X
и
Y
— выходные данные, полученные до и после исключения
функционального свойства.
Если результат формулы (14) не будет нулевым, то исключенное
функциональное свойство будет существенным. Очевидно, что задача
определения существенности функционального свойства сводится к
задаче выполнимости булевской формулы, а следовательно, лежит в
классе
NP
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 99
