Представление булевой функции полиномом

Предположим, у нас есть булева функция из . Ясно, что вещественный многомерный полином p ( x ) такой, что f ( x ) = p ( x ) на x ∈ { 0 , 1 } n, может быть полилинейным. Какие интересные классы булевых функций, для которых минимальная степень р ( х $f:\{0,1\}^n\rightarrow\{0,1\}$$p(x)$$f(x)=p(x)$$x\in\{0,1\}^n$$p(x)$известен? У нас есть конкретные примеры?

$n$

$d$$d2^d$$d = 1$

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

1. Псевдобулевы функции над вещественными числами (теорема 1.34 [1])

2. $[0,1]^n$

Фон

«Каждая булева функция может быть представлена ​​дизъюнктивной нормальной формой и конъюнктивной нормальной формой». (Теорема 1.4 (с.16 [1])

$\vee (\wedge {x} \wedge \bar{x} )$$\vee (\prod x \prod (1-x))$$\sum c \prod x$$F$$\mathcal B^n$$\mathcal P(N)$$\oplus$$f(x_1,\ldots,x_n)=\oplus_{A\in\mathcal P(N)} c(A)\prod_{i\in A} x_i$

и их приложения содержат

• $[0,1]^n$

• $[0,1]^n$

• (схемы) Сложность булевой функции многолинейного полиномиального вычисления

• (анализ Фурье) Нижние оценки для полиномов, вычисляющих булевы функции

Ссылки

[1] Теория, алгоритмы и приложения булевых функций (Ив Крама, Питер Л. Хаммер, 2011)