Определение
Приводимое здесь определение сформулировано В. А. Захаровым.
Эффективное вычисление - это вычисление, требующее полиномиального от длины входа времени и полиномиальной от длины входа памяти. Эффективная программа (машина Тьюринга) - программа, работающая полиномиальное от длины входа время и требующая полиномиальную от длины входа рабочую память на всех входах, на которых программа завершается.
Пусть П - множество всех программ (машин Тьюринга), удовлетворяющих сформулированным выше ограничениям, и пусть программа pП вычисляет функцию
подмножество
называется функциональным свойством если
Пусть - функциональное свойство, - класс программ такой, что существует эффективная программа с такая, что для любой программы
Другими словами, для функционального свойства
мы определяем класс программ Р таких, что существует эффективная программа-распознаватель с свойства по программе р из класса Р . Вероятностная программа о называется запутывателем класса Р относительно свойства ,(Р,)-запутывателем, если выполняются условия: a) (эквивалентность преобразования запутывания). Для любой и
Здесь у=poly(x) означает, что y ограничен полиномом некоторой степени от переменной x ,timep(x) - время выполнения программы p на входе x , |p| - размер программы p.
b) (трудность определения свойств по запутанной программе). Для любого полинома q и для любой программы (вероятностной машины Тьюринга) a такой, что a(o(P))={0,1} , и для любой
выполняется timea(o(p))=poly(|o(p)|), существует программа (вероятностная машина Тьюринга с оракулом) b , и при этом для любой .
Другими словами, вероятность определить свойство
по запутанной программе равна вероятности определения свойства только по входам и выходам функции . То есть, наличие текста запутанной программы ничего не даёт для выявления свойств этой программы.
Универсальный запутыватель - это программа O , которая для любого класса программ P и любого свойства
является (P, )-запутывателем. Как показано в работе [2], универсального запутывателя не существует. Доказательство заключается в построении специального класса программ P и выборе такого свойства , что для любого преобразования программы из этого класса свойство устанавливается легко. Однако вопрос о том, существуют ли запутыватели для отдельных классов свойств программ, и насколько широки и практически значимы эти классы свойств, остаётся открытым. С практической точки зрения запутывание программы можно рассматривать как такое преобразование программы, которое делает её обратную инженерию экономически невыгодной. Несмотря на слабую теоретическую проработку, уже разработано большое количество инструментов для запутывания программ.
Содержание раздела
