сложность декомпозиции векторной булевой функции

[retis]

Есть у нас булевая векторная функция (нелинейная) $\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)$ или свести к какой-то более известной задаче или показать, что с меньшей сложностью она не решиться?

[retis]

Появилась идея переформулировки.
Любую БФ размера $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}$ (более того, эти пары есть разбиением множества всех коефициентов).
Тем не менее, сложность задачи неясна.

[retis]

Возникла еще идея решения.
Допустим, у нас матрица $||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$).
Обратное сведение у меня получается. Есть у кого-то дальнейшие идеи?