Аннотация:
Пусть $F_p$ — поле, состоящее из $p$ элементов, $p$ — простое, и задана функция $\varphi\colon F_p^n \to F_p$. Существуют ли такие подпространства $U,V\subset F_p^n$ и функции $\psi\colon U\to F_p$, $\chi\colon V\to F_p$, что $F_p^n$ есть прямая сумма $U$ и $V$ и $\varphi(u+v)=\psi(u)+\chi(v)$ при всех $u\in U$, $v\in V$? Построен алгоритм для проверки выполнения этого условия, который имеет сложность не выше полинома от $p^n\log p$.
|
