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


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


Обозначим WinA решение, найденное алгоритмом A для f1.

Пусть xk - существенная переменная. Тогда Win0 таково, что 1+1

|Win0|
l*m , WinA таково, что , а удовлетворяет неравенству 1+1
|WinA|
l*m.

Пусть xk - несущественная переменная. Тогда Win0 таково, что 0

|Win0|
m-1, Win1 таково, что 0
|Win1|
m-1 , а WinA удовлетворяет неравенству 0
|WinA|
p*(m-1) .

Заметим, что p*(m-1)< l+1 =m*[p]+1 . В зависимости от WinA, полученного полиномиальным p-приближённым алгоритмом A мы можем определить, является ли xk существенной переменной или нет. Следовательно, P=NP.

Определение 7. Назовём "мёртвыми" все инструкции, которые относятся к вычислению несущественных переменных.

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

Переменные произвольных целых типов могут рассматриваться как набор переменных булевского типа. Например, переменная типа int может рассматриваться как 32 булевские переменные, для доступа к которым используются битовые операции.




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



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