2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 сложность декомпозиции векторной булевой функции
Сообщение08.09.2015, 16:05 


08/09/15
4
Есть у нас булевая векторная функция (нелинейная) $\varphi: V_n \to V_n$ и линейное преобразование (матрица над полем $F_2$): $A: V_n \to V_n$.
Но нам известна только композиция функций $\rho = \varphi \circ A \times \varphi^{-1}$ (скажем, в виде столбика из n полиномов Жегалкина).
1) нужно найти $\varphi$ и матрицу $A$.
2) найти любые (вариант - все) булевую векторную функцию и матрицу $\psi$ и $B$ такие, что $\rho = \psi \circ B \times \psi^{-1}$
Понятно, что перебором можно решить задачу со сложностью $2^n!$ (ко-во биективных функций размерности n).
Вопрос в том, возможно ли это сделать с меньшей сложностью (скажем, $O((2^n)^C)$ или свести к какой-то более известной задаче или показать, что с меньшей сложностью она не решиться?

 Профиль  
                  
 
 Re: сложность декомпозиции векторной булевой функции
Сообщение16.09.2015, 14:15 


08/09/15
4
Появилась идея переформулировки.
Любую БФ размера $n\times n$ можно представить в виде матрицы перестановки размера $2^n \times 2^n$.
Допустим, мы знаем $A$ (или перебираем по очереди. Это все равно меньше, чем перебирать все $\varphi$). Тогда задача сведется к поиску перестановочной матрицы $X: X\times A = P\times X$, где $P$ - представление БФ $\rho$ через матрицу перестановки. Либо же к задаче нахождения любой перестановочной матрицы $X$ при том, что известны некоторые пары равных коефициентов: $\{x_{i_k}=x_{j_k}\}_{k=1..n^2/2}$ (более того, эти пары есть разбиением множества всех коефициентов).
Тем не менее, сложность задачи неясна.

 Профиль  
                  
 
 Re: сложность декомпозиции векторной булевой функции
Сообщение23.09.2015, 11:33 


08/09/15
4
Возникла еще идея решения.
Допустим, у нас матрица $||x_{i,j}||$ размером $n\times n$ и на ней заданы $k: k \le \frac{n^2}{2}$ пар равенств коефициентов.
Определим вектор $V$ размерности $n$ для каждого условия $x_{i_1,j_1}=x_{i_2,j_2}$ (если $i_1\ne i_2$ и $j_1 \ne j_2$) таким образом:
    1. $v_k = 0, \forall k = 1..n, k \ne i_1, k \ne i_2$
    2. $v_{i_1} = j_1$
    3. $v_{i_2} = j_2$
Для всех коефициентов $x_{i,j}$, которые не состоят в равенствах, вектор задается так:
    1. $v_k = 0, \forall k = 1..n, k \ne i_1, k \ne i_2$
    2. $v_{i} = j$

Далее, считаем вектора $\vec{A}$ и $\vec{B}$ совместимыми, если $\forall i=1..n: a_i = 0 \vee b_i = 0, a_i \in A, b_i \in B$ и значения в векторах не повторяются (кроме 0). В таком случае, если мы найдем $n$ попарно совместимых векторов - они точно будут соответствовать строкам перестановочной матрицы. Но может быть и меньшее количество (если к-во пар коефициентов, задействованых в условиях, будет ровно $\frac{n^2}{2}$, то требуется уже всего $\frac{n}{2}$ совместимых векторов).
Т.е., считая вектора вершинами графа, а совместимость - ребрами, можно свести решение задачи к решению задачи о k-клике (для $\frac{n}{2} \le k \le n$).
Обратное сведение у меня получается. Есть у кого-то дальнейшие идеи?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group