Помогите плиз решить задачку по дискре! =) [булевы функции, сложность]

svetik5623190

Итак, задачка.
Пусть A - множество всех таких булевых функций f(x_1, ..., x_n, y_1, ...,y_n, z_1, ...., z_n) от 3n булевых переменных, что можно при любом фиксированном k сделать любую перестановку в переменных x_k, y_k, z_k и значение f не изменится.
Требуется найти max L(f) при f из А. L(f) - схемная сложность, т.е. минимальное число элементов, из которых можно построить схему, вычисляющую f.
Собственно вот и всё.
Что уже удалось понять: f фактически зависит только от 2n новых булевых переменных из-за симметрии. Действительно, если в тройке x_k, y_k, z_k переменные можно переставлять как угодно, то фактически f зависит только от числа единиц среди значений переменных в этой тройке, т.е. от их суммы x_k + y_k + z_k, которая может принимать значения только 0,1,2,3 - всего 4 значения, чтобы их описать надо 2 бита, т.е. 2 булевы переменные а не 3.
Что делать дальше - не знаю. Пожалуйста помогите/намекните кто понимает в чём тут суть :)
Заранее спасибо!

toxin

Ну собственно ты все уже решил. Вычисление новых переменных - [math]O(n)[/math]. Схемная сложность функции от n переменных асимптотически равна 2^n/\ln(n). Соотвественно ответ асимптотически равен 2^{2n}/\ln(n). А точный ответ вычислить не возможно (без использования [math]L(n)[/math]).
PS Не забудь показать, что задачи равносильны - т.е. их можно сводить одну к другой в обе стороны.

Alexx13

В качестве базиса (полной системы) можно взять базис всех двуместных булевых функций (как это принято в технике); тогда сложность уменьшится.

svetik5623190

Спасибо большое, буду обдумывать :)
Оставить комментарий
Имя или ник:
Комментарий: