Merupakan fungsi boolean oleh polinomial

10

Misalkan kita memiliki fungsi boolean dari . Jelas bahwa nyata multivariat polinomial sehingga pada bisa multilinear. Apa sajakah kelas fungsi boolean yang menarik di mana tingkat minimal $f:\{0,1\}^n\rightarrow\{0,1\}$ $p(x)$ $f(x)=p(x)$ $x\in\{0,1\}^n$ $p(x)$ dikenal? Apakah kita punya contoh nyata?

boolean-functions T ....
sumber

2

Terkait: cstheory.stackexchange.com/questions/25291/…

Andrej Bauer

1

Jika Anda tidak terbiasa dengan itu, terkait erat adalah banyak pekerjaan pada "derajat perkiraan", yang bertanya, apa tingkat minimal polinomial yang "mendekati"

? Saya tidak cukup tahu untuk memberikan referensi spesifik tetapi yang lain akan.

f

$f$

usul

10

$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$

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

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

f

$f$

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

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

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

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

\prod_{i} x_{i}

$\prod_i x_i$

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

Yuval Filmus
sumber

Ini adalah poin yang berguna. Apa referensi yang bagus untuk topik ini?

T ....

3

Anda dapat melihat buku terbaru Ryan O'Donnell, Analysis of Boolean functions.

Yuval Filmus

0

Kelas fungsi Boolean dengan isi presentasi multilinear unik

Fungsi Pseudo-Boolean melebihi real (Teorema 1.34 [1])
$[0,1]^n$

Latar Belakang

"Setiap fungsi Boolean dapat diwakili oleh bentuk normal disjungtif dan dengan bentuk normal konjungtif." (Teorema 1.4 (hal.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$

dan aplikasi mereka mengandung

$[0,1]^n$
$[0,1]^n$
(sirkuit) Kompleksitas fungsi Boolean komputasi polinomial multi-linier
(Analisis fourier) Batas bawah untuk Polinomial menghitung fungsi boolean

Referensi

[1] Teori Fungsi Boolean, Algoritma, dan Aplikasi (Yves Crama, Peter L. Hammer, 2011)

hhh
sumber

1

Ya tentu saja. Sekarang, bagaimana itu menjawab pertanyaan?

Emil Jeřábek

Merupakan fungsi boolean oleh polinomial

Jawaban: