论文标题
有界重复和有限宽度的CNF的分支程序的分裂能力
The splitting power of branching programs of bounded repetition and CNFs of bounded width
论文作者
论文摘要
在本文中，我们研究了代表有界树宽的CNF的有界重复的句法分支程序。为此，我们介绍了两个新的结构图参数$ d $ - pathwidth和clique的保留$ d $ - pathwidth，由$ d-pw（g）$和$ d-cpw（g）$表示，其中$ g $是图形。我们表明，$ 2-CPW（g）\ leq O（tw（g）δ（g））$，其中$ tw（g）$和$δ（g）$分别是$ g $的树宽和最大度。使用此上限，我们证明了每个CNF $ψ$可以表示为两个尺寸$ 2^{o（δ（ψ）*TW（ψ）^2）} $的连接，其中$ tw（ψ）$是$ψ$的原始图的tw（ψ）$，每个可变的$ψ$ and $ψ$的原始图是$ψ$的$Δ（ψ）（ψ）（ψ） 接下来，我们使用$ d $ -Pathwdith获取单调分支程序的下限。特别是，我们考虑了句法非确定性的单调版本读取$ d $ t $ times分支程序（仅禁止负面文字作为边缘标签），并引入了进一步的限制，即每个计算路径最多都可以分配到最多$ d $ d $ read-once-once subpaths。我们称结果模型可分开的单调读取$ D $ times分支程序，并缩写为$ d $ -smnbps。对于无孤立顶点的每个图形$ g $，我们引入了cnf $ψ（g）$ WHSOSE子句为$（u \ vee e \ vee v）$ e = \ e = \ {u，v \} $的$ g $。我们证明，代表$ψ（g）$的$ d $ -smnbp至少$ω（c^{d-pw（g）}）$，其中$ c =（8/7）^{1/12} $。我们使用此“通用”下限来获得CNFS $ψ（k_n）$的“混凝土”类别的指数下限。特别是，我们证明，对于$ 0 <a <1 $，$ n^{a} $ -smnbp的大小代表$ψ（k_n）$至少是$ c^{n^b} $，其中$ b $是一个任意的常数，因此$ a+b <1 $。从意义上讲，该下限$ψ（k_n）$可以用多大小$ n $ -smnbp表示。
In this paper we study syntactic branching programs of bounded repetition representing CNFs of bounded treewidth. For this purpose we introduce two new structural graph parameters $d$-pathwidth and clique preserving $d$-pathwidth denoted by $d-pw(G)$ and $d-cpw(G)$ where $G$ is a graph. We show that $2-cpw(G) \leq O(tw(G) Δ(G))$ where $tw(G)$ and $Δ(G)$ are, respectively the treewidth and maximal degree of $G$. Using this upper bound, we demonstrate that each CNF $ψ$ can be represented as a conjunction of two OBDDs of size $2^{O(Δ(ψ)*tw(ψ)^2)}$ where $tw(ψ)$ is the treewidth of the primal graph of $ψ$ and each variable occurs in $ψ$ at most $Δ(ψ)$ times. Next we use $d$-pathwdith to obtain lower bounds for monotone branching programs. In particular, we consider the monotone version of syntactic nondeterministic read $d$ times branching programs (just forbidding negative literals as edge labels) and introduce a further restriction that each computational path can be partitioned into at most $d$ read-once subpaths. We call the resulting model separable monotone read $d$ times branching programs and abbreviate them $d$-SMNBPs. For each graph $G$ without isolated vertices, we introduce a CNF $ψ(G)$ whsose clauses are $(u \vee e \vee v)$ for each edge $e=\{u,v\}$ of $G$. We prove that a $d$-SMNBP representing $ψ(G)$ is of size at least $Ω(c^{d-pw(G)})$ where $c=(8/7)^{1/12}$. We use this 'generic' lower bound to obtain an exponential lower bound for a 'concrete' class of CNFs $ψ(K_n)$. In particular, we demonstrate that for each $0<a<1$, the size of $n^{a}$-SMNBP representing $ψ(K_n)$ is at least $c^{n^b}$ where $b$ is an arbitrary constant such that $a+b<1$. This lower bound is tight in the sense $ψ(K_n)$ can be represented by a poly-sized $n$-SMNBP.
