Reprezentująca funkcję logiczną przez wielomian

10

Załóżmy, że mamy funkcję boolowską od . Oczywiste jest, że prawdziwy wielomianowy wielomian taki, że na może być wieloliniowy. Jakie są ciekawe klasy funkcji boolowskich, dla których minimalny stopień $f:\{0,1\}^n\rightarrow\{0,1\}$ $p(x)$ $f(x)=p(x)$ $x\in\{0,1\}^n$ $p(x)$ jest znana? Czy mamy konkretne przykłady?

boolean-functions

— T ....
źródło

2

Powiązane: cstheory.stackexchange.com/questions/25291/…

— Andrej Bauer

1

Jeśli nie jesteś z tym zaznajomiony, ściśle powiązane jest dużo pracy nad „przybliżonym stopniem”, który pyta, jaki jest minimalny stopień wielomianu, który „przybliża”

? Nie wiem wystarczająco, aby podać konkretne referencje, ale inni by to zrobili.

f

$f$

— usul

10

Każda funkcja, która ma niezerową korelację z parzystością ma stopień . Oznacza to, że jeśli wówczas unikalne wieloliniowe rozszerzenie zawiera monomial . Rzeczywiście, ponieważ $n$

\sum_{x \in {0, 1}^{n}} (- 1)^{\sum_{i} x_{i}} f (x) \neq 0

$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$

f

$f$

x_{1} \dots x_{n}

$x_1\cdots x_n$

, rozszerzenie Fouriera

(wyrażonejako iloczyn iloczynu

(- 1)^{x_{i}} = \frac{1 - x_{i}}{2}

$(-1)^{x_i} = \frac{1-x_i}{2}$

f

$f$

) będzie zawierać termin

\frac{1 - x_{i}}{2}

$\frac{1-x_i}{2}$

i odpowiadające Jednomian

nie pojawia się w każdym innym czasie.

\prod_{i} \frac{1 - x_{i}}{2}

$\prod_i \frac{1-x_i}{2}$

\prod_{i} x_{i}

$\prod_i x_i$

Nisan i Szegedy udowodnili, że funkcje stopnia zależą co najwyżej od zmiennych . Dla możemy być dokładniejsi: funkcja musi zależeć co najwyżej od jednej współrzędnej. $d$ $d2^d$ $d = 1$

— Yuval Filmus
źródło

To przydatny punkt. Jakie jest dobre odniesienie do tego tematu?

— T ....

3

Możesz rzucić okiem na ostatnią książkę Ryana O'Donnella, Analiza funkcji boolowskich.

— Yuval Filmus

0

Zawierają klasy funkcji boolowskich z unikalną prezentacją wieloliniową

Funkcje pseudoloolowe nad rzeczywistymi (Twierdzenie 1.34 [1])
Funkcja boolowska nad jednostką kostki $[0,1]^n$

tło

„Każda funkcja boolowska może być reprezentowana przez rozłączną postać normalną i przez koniugacyjną postać normalną”. (Twierdzenie 1.4 (p.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$

a ich aplikacje zawierają

$[0,1]^n$
$[0,1]^n$
(obwody) Złożoność wieloliniowego obliczania wielomianowego Funkcja boolowska
(analiza Fouriera) Dolne granice dla wielomianów obliczających funkcje boolowskie

Bibliografia

[1] Teoria, algorytmy i zastosowania funkcji logicznych (Yves Crama, Peter L. Hammer, 2011)

— hhh
źródło

1

Tak, oczywiście. Jak to odpowiada na pytanie?

— Emil Jeřábek