We show that the coefficients of the representing polynomial of any monotone Boolean function are the values of a Moebius function of an atomistic lattice related to this function. Using this we determine the representing polynomial of any Boolean function corresponding to a direct acyclic graph connectivity problem. Only monomials corresponding to unions of paths have non-zero coefficients which are $(-1)^D$ where $D$ is an easily computable function of the graph corresponding to the monomial (it is the number of plane regions in the case of planar graphs). We estimate the number of monomials with non-zero coefficients for the two-dimensional grid connectivity problem as being between $\Omega(1.641^{2n^2})$ and $O(1.654^{2n^2})$.
翻译：我们显示,代表任何单调布尔函数的多元值系数是与此函数相关的原子阵列的Moebius函数的值。 我们使用这个系数来确定与直接环形图形连接问题相对应的任何布尔函数的多元值。 只有与路径交错的单数具有非零系数, 即$( 1)\D$, 其中$( $) 是单数( 平面图中平面区域的数量) 。 我们估计二维网格连接问题中带有非零系数的单数在$( Omega( 1.641) ⁇ 2n ⁇ 2}) 和$( O) (1.654) ⁇ 2} 之间。
相关内容
微信扫码咨询专知VIP会员