1

Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be a boolean function.

Let $d$ be the smallest degree of $f(x_1,x_2,\dots,x_n)\in \mathbb R[x_1,x_2,\dots,x_n]$ that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $f(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$).

Is there a candidate boolean function $P(x_1,x_2,\dots,x_n)$ such that the smallest degree of $r(x_1,x_2,\dots,x_n)\in \mathbb R(x_1,x_2,\dots,x_n)$ (sum of degrees of numerator and denominator) that represents $P(x_1,x_2,\dots,x_n)$ (where represents means $R(x_1,x_2,\dots,x_n)$ and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$) is $d^a$ for some $a\in(0,1)$?

Note that $f(x_1,x_2,\dots,x_n)$ and the numerator and denominator of $r(x_1,x_2,\dots,x_n)$ can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.

Turbo
  • 12,812
  • 1
  • 19
  • 68

0 Answers0