Some structural properties of quadratic boolean threshold functions.pdf Полиномиальные булевы пороговые функции определяются следующим образом [1]: f(xi,... ,xn) = 0 ^ g(xi,... ,xn) ^ 0, (1) где g - действительный полином. Если deg g = 2, то говорят о к.б.п.ф. В последнем случае неравенство из (1) может быть преобразовано в эквивалентное q(xi,... , xn) ^ t, где q - квадратичная форма, а t - свободный член многочлена g, взятый с противоположным знаком и называемый порогом. Пусть = {{w(x) : x е {0,1}n}} -мультимножество значений квадратичной формы w(x). Через {Aw} обозначается множество значений w(x). Под набором w* = = (w0, w*... , w*n_i) понимается набор упорядоченных по неубыванию элементов множества . В тексте без особых оговорок используются обозначения из [2] для линейных булевых пороговых функций, которые без изменения переносятся на полиномиальный случай. В частности, факт, что к.б.п.ф. задаётся квадратичной формой q и порогом t, для краткости записывается как f ~ (q,t). Имея две квадратичные формы от независимых переменных- p(x) и q(y), можно составить новую квадратичную форму h(x, у) = p(x) + q(y) (будем обозначать h = p|q). Рассмотрим бинарное отношение частичного порядка на множестве действительных квадратичных форм. Если q* является подпоследовательностью r* для квадратичных форм q(x) и r(y) (возможно, от разного числа переменных, но все переменные из x входят в у), то будем обозначать этот факт как q r. В дальнейшем без ограничения общности будем полагать все веса целыми числами. Важность введённого бинарного отношения по отношению к изучению функциональной структуры к.б.п.ф. следует из следующего утверждения. Утверждение 1 [2]. Пусть к.б.п.ф. f ~ (pi|qi,t) и g ~ (p2|q2,t) удовлетворяют свойству pi - p2, qi - q2. Тогда если g допускает простую декомпозицию, то и f допускает простую декомпозицию. Под нетривиальной простой декомпозицией понимается следующая бесповторная суперпозиция для некоторого m е {2,...,n - 1}: f (xi, . . . ,xn) = ^(^(xi, . . . ,xm),xm+i, . . . ,xn) . Утверждение 1 позволяет предложить способ построения классов функционально разделимых (или функционально неразделимых) к.б.п.ф., равно как и подход к анализу функциональной разделимости заданной к.б.п.ф. Пусть {м»} и {г»} -множества квадратичных форм от m, и n, переменных (m,, n, > 1), имеющие верхние грани u и v относительно введённого бинарного отношения. Тогда если пороговая функция со структурой (u|v,t) функционально разделима, то и любая пороговая функция со структурой (u,|v,, t) также функционально разделима. Справедливо и отрицание этого утверждения. Замечание 1. Утверждение 1 и вышеприведённые рассуждения не зависят от вида неравенства, задающего пороговую функцию, и поэтому справедливы для полиномиальных пороговых функций. Для целочисленной матрицы W квадратичной формы определим троичное представление - матрицу UW = (uW)i,j=1,...,N некоторой квадратичной формы uW, задаваемую следующим образом. Элементу wj матрицы W в матрице UW соответствует клетка размера х j, причём клетки не пересекаются и расположены в том же порядке, что и сами элементы w,j в матрице W. Натуральные числа , i = 1,...,n, удовлетворяют условиям /j/j ^ |wij |, n (2) N = Е ^ min. i=1 В каждой клетке произвольным образом (с сохранением свойства симметричности матрицы UW) расставляются единицы в случае wj > 0 и -1 для wj < 0. Остальные элементы полагаются равными нулю. Троичное представление всегда существует, например, можно положить /j = max wj, хотя в этом случае условие минимальности je{1,...,ra} размера N троичного представления не обязательно выполняется. Несмотря на то, что минимизация размера N полезна в практическом смысле, использование троичного представления не связано строго с этим свойством, поэтому в дальнейшем под троичным представлением также будем понимать и неоптимальные по размеру матрицы. Дополнительный способ сокращения размера троичного представления связан с переходом к матрице W = - W, где d =НОД^у}. Задача (2) относится к задачам целочисленного квадратичного программирования с линейной целевой функцией. Путём перехода к величинам r, = log /, эта задача приобретает вид задачи линейного программирования в дискретной решётке log N. Для решения последней задачи с учётом необязательности выполнения требования оптимальности может быть применён полиномиальный алгоритм Хачияна [3] с последующим «округлением» результата в ближайший узел решётки. Отсутствие требования оптимальности делает возможным использование приближённых алгоритмов решения задачи целочисленного программирования [4, 5]. Из определения троичного представления и предшествующих рассуждений следует его неоднозначность. Другое важное свойство заключается в том, что если для булева вектора a = (a1,..., an) положить компоненты булева вектора b = (b1,..., ) в соответствии с условием a, = 1 ^ b1l+...+1i_1+1 = ... = b1l+...+1i = 1, то w(a) = aWaT = bUW bT = uW (b). (3) Справедливость (3) следует из того, что серии нулей и единиц в векторе b соответствуют клеткам матрицы UW. Следовательно, коэффициенты wj, участвующие в вычислении (т. е. индексы i и j, такие, что a, = aj = 1), соответствуют клеткам с суммарным количеством элементов равным sgn(wj-)|wj- |. Таким образом, доказано Утверждение 2. Справедливы следующие отношения: 1) w - uW; 2) w - duW, где d =НОД^}. Представляет интерес описание функциональной структуры к.б.п.ф с матрицей квадратичной формы, имеющей вид троичного представления. Для этого, в частности, рассмотрим вопрос о существенных переменных к.б.п.ф. с матрицами квадратичных форм простого вида. Пусть 1n - целочисленная квадратная матрица размера n, состоящая из одних единиц. Легко видеть, что {Ain } = {k2 : k = 0,... , n}. Утверждение 3. К.б.п.ф. f ~ (1n,t), отличная от константы, зависит существенно от всех своих переменных. Доказательство. Так как функция f симметричная, достаточно доказать утверждение для первой переменной. Пусть для некоторого s выполняется t е [s2, (s + 1)2). Такое 0 ^ s ^ n - 1 существует всегда, так как по условию 0 ^ t < n2. Тогда выполняются неравенства w(0, а) = s2 ^ t и w(1, а) = s2 + 2n - 1 ^ (s + 1)2 > t, где а - произвольный вектор размера n - 1 c весом s. ■ Рассмотрим структурные свойства к.б.п.ф. f ~ (1m|1n-m,t), где 1 ^ m ^ n - 1. Утверждение 4. К.б.п.ф. f ^ (1m 11n_m, t) зависит существенно от первых ^^ (1 ^ m ^ n - 1) переменных, если и только если найдутся такие r е {0,... ,m - 1}, s е {0,... , n - m}, что выполняется система неравенств r2 + s2 ^ LtJ, (r + 1)2 + s2 ^ ftl, 22 ^ i /., , \ 2 , 2 w ^ (4) где квадратичная форма w = (1m|1n-m); |_tJw и [t]w -нижние и верхнее приближения числа t в множестве {Aw} [2]. Доказательство. Без ограничения общности будем рассматривать существенную зависимость функции f от первой переменной. Докажем утверждение, заменив (4) на равносильную систему r2 + s2 ^ t< (r + 1)2 + s2. (5) Действительно, по свойствам верхнего и нижнего приближений |_tJw ^ t < [t]w, поэтому из (4) следует (5). Так как r2 + s2, (r + 1)2 + s2 е {Aw}, то справедлива и обратная импликация. Достаточность. Если для некоторых r е {0,... , m - 1} и s е {0,... , n - m} выполняется (4), то значения функции f на булевых векторах (0, м, г) и (1, м, г) различаются, где м - произвольный вектор длины m - 1 и веса r, а г - произвольный вектор длины n - m веса s. Действительно, w(0,м, г) = r2 + s2 ^ t < (r + 1)2 + s2 = w(1, м,г). Необходимость. Пусть от противного выполняется отрицание (5), т.е. для каждой пары (r, s) верно t < r2 + s2 или t ^ (r + 1)2 + s2, что в силу неравенств t < r2 + s2 < < (r + 1)2 + s2 и t ^ (r + 1)2 + s2 > r2 + s2 равносильно совпадению значений функции на произвольных векторах (0, м, г) и (1, м, г), т. е. несущественной зависимости функции f от первой переменной. ■ Следствие 1. К.б.п.ф f ~ (1111n-1, t) зависит существенно от первой переменной тогда и только тогда, когда k2 ^ t < k2 + 1 для некоторого k е {0,...,n - 1}. Пример 1. К.б.п.ф. f ~ (1i|13, 2) зависит несущественно от первой переменной. Её таблица истинности и многочлен Жегалкина такие же, как для пороговой функции ((1,1,1), 1), т. е. x2x3 + x2x4 + x3x4. Пример 2. К.б.п.ф. gi ~ (12|13, 8) имеет многочлен Жегалкина ж3ж4ж5, хотя при порогах 7 или 9 с той же матрицей квадратичной формы соответствующие функции g2 и g3 зависят существенно от всех пяти переменных и имеют многочлены Жегалкина xix2x3x4 + xix2x3x5 + xix2x4x5 + x3x4x5 + xix2x3x4x5 и xix3x4x5 + x2x3x4x5 + xix2x3x4x5 соответственно. При этом функция gi является линейной пороговой со структурой ((0, 0,1,1,1), 2), а функции g2 и g3 -линейными пороговыми со структурами ((1,1, 3, 3, 3), 7) и ((1,1, 3, 3, 3), 9) соответственно. Кроме того, обе функции допускают декомпозиции g2 = xix2(x3x4 + x3x5 + x4x5 + x3x4x5) и g3 = (xi + x2 + xix2)x3x4x5. Приведённые примеры показывают, что даже в случае очень простых квадратичных форм задаваемые ими к.б.п.ф. могут сильно отличаться в смысле существенной зависимости от переменных при небольших (последовательных) изменениях порога. Кроме того, интерес представляет нахождение пороговой степени (см. определение в [1]) к.б.п.ф. В заключение отметим, что даже для линейной пороговой булевой функции задача определения существенной зависимости переменной является NP-полной [6, теорема 9.26, с. 436], что повышает значимость разработки эвристических методов её решения.

Скачать электронную версию публикации