论文标题
近似布尔函数的脱节正常形式
Approximating Boolean Functions with Disjunctive Normal Form
论文作者
论文摘要
该定理指出：每个布尔函数都可以通过大小$o_ε（2^{n}/\ log {n}）$的析取常规形式（DNF）$ε-Approximated $。本文将通过展示如何生成该定理并证明其正确性来详细说明该定理。我们还将潜入一些特定的布尔函数，并探讨这些布尔函数如何由DNF近似，该功能的大小在通用界限$o_ε（2^{n}/\ log {n}）$中。我们感兴趣的布尔函数是：奇偶校验函数：奇偶校验函数可以是$ε -Appro -approximated $，宽度$（1-2ε）n $和size $ 2^{（1-2ε）n} $。此外，我们将探索DNF大小和宽度的下限。多数函数：对于每个常数$ 1/2 <ε<1 $，都有一个尺寸$ 2^{o（\ sqrt {n}）} $的DNF，可以$ε-approximated $在n位上的多数函数。单调函数：每个单调函数f可以为$ε -Approximated $ by dnf g的dnf g $ 2^{n -ωε（n）} $满足$ g（x）\ le f（x）$ for All x。
The theorem states that: Every Boolean function can be $ε-approximated$ by a Disjunctive Normal Form (DNF) of size $O_ε(2^{n}/\log{n})$. This paper will demonstrate this theorem in detail by showing how this theorem is generated and proving its correctness. We will also dive into some specific Boolean functions and explore how these Boolean functions can be approximated by a DNF whose size is within the universal bound $O_ε(2^{n}/\log{n})$. The Boolean functions we interested in are: Parity Function: the parity function can be $ε-approximated$ by a DNF of width $(1 - 2ε)n$ and size $2^{(1 - 2ε)n}$. Furthermore, we will explore the lower bounds on the DNF's size and width. Majority Function: for every constant $1/2 < ε< 1$, there is a DNF of size $2^{O(\sqrt{n})}$ that can $ε-approximated$ the Majority Function on n bits. Monotone Functions: every monotone function f can be $ε-approximated$ by a DNF g of size $2^{n - Ωε(n)}$ satisfying $g(x) \le f(x)$ for all x.
