Representando a função booleana por um polinômio

10

Supondo que tenhamos uma função booleana de . É claro que um polinômio multivariado real tal que em pode ser multilinear. Quais são algumas classes interessantes de funções booleanas para as quais o grau mínimo de é conhecido? Temos exemplos concretos?p ( x ) f ( x ) = p ( x ) x { 0 , 1 } n p ( x )f:{0,1}n{0,1}p(x)f(x)=p(x)x{0,1}np(x)

T ....
fonte
11
Se você não está familiarizado com isso, há muito trabalho relacionado ao "grau aproximado", que pergunta: qual é o grau mínimo de um polinômio que "se aproxima" de ? Não sei o suficiente para dar referências específicas, mas outros o fariam. f
usul 13/10

Respostas:

10

Qualquer função que tenha correlação diferente de zero com paridade tem o grau . Ou seja, se , a expansão multilinear exclusiva de contém o monômio . De fato, como , a expansão de Fourier de (expressa em termos de produtos de ) conterá o termo , e o monômio correspondente não aparece em nenhum outro termo.n

x{0,1}n(1)ixif(x)0
fx1xn(1)xi=1xi2f1xi2i1xi2ixi

Nisan e Szegedy provaram que funções de grau dependem de no máximo variáveis. Para , podemos ser mais precisos: a função deve depender de no máximo uma coordenada.d 2 ddd2dd=1

Yuval Filmus
fonte
Este é um ponto útil. O que é uma boa referência para este tópico?
T ....
3
Você pode dar uma olhada no livro recente de Ryan O'Donnell, Analysis of Boolean functions.
Yuval Filmus 14/10
0

Classes de funções booleanas com apresentação multilinear exclusiva contêm

  1. Funções pseudo-booleanas sobre reais (teorema 1.34 [1])

  2. Função booleana sobre o cubo unitário [0,1]n

fundo

"Toda função booleana pode ser representada por uma forma normal disjuntiva e por uma forma normal conjutiva". (Teorema 1.4 (p.16 [1])

portanto, toda forma normal disjuntiva (DNF) da forma pode ser escrita como e e definições adicionais na página 18 do livro, como subscritos. Você pode representar todas as funções booleanas em em termos de powerset e soma direta modo que (THM1.33).( Π x Π ( 1 - X ) ) Σ c Π x F B n P ( N ) f ( x 1 , ... , x n ) = Um P ( N ) c ( A ) Π i Um x i(xx¯)(x(1x))cxFBnP(N)f(x1,,xn)=AP(N)c(A)iAxi

e suas aplicações contêm

Referências

[1] Teoria, algoritmos e aplicações de funções booleanas (Yves Crama, Peter L. Hammer, 2011)

hhh
fonte
11
Sim, obviamente. Agora, como isso responde à pergunta?
Emil Jerabek