MMNov, 2014

关于有限树宽分支程序和 CNF 的一次性读取特性

PDF
TL;DR通过证明经过单次读取分支程序（nrobp）的空间下限为 n^Ω(k)，针对原始图的树宽不超过 k 的 cnfs 可证明 nrobp 的固定参数空间复杂性不可行，在此基础上我们得到自由二元决策图和决策可分解否定正常形式之间的近多项式分离。
read-once branching programsnon-deterministicspace complexitytreewidthsyntactic
发现论文，激发创造
  • 关于有界树宽的 CNFs 的 OBDDs

    本文表明，CNF 无法被编译成由原始图树宽参数化的固定参数大小的有序二元决策图（OBDD）。因此，我们为 OBDD 和 SDD 提供了参数化分离，并证明了所提出的下界还可以产生 OBDD 和 SDD 的古典（非参数化）分离。此外，我们还展示了对于 OBDD 的现有的最佳参数化上界实际上适用于关联图树宽参数化。

    Aug, 2013

  • 精确模型计数的下界及在概率数据库中的应用

    本文研究了用于准确计算布尔公式的确定性决策图 (d-DNNF) 表示法，将其转换为自由二叉决策图 (FBDD) 用于提供计算上限，并证明了决策 - DNNF 的指数下限，从而提高了关联概率数据库的计算效率。

    Sep, 2013

  • 团宽和知识编译

    本文研究了丛图宽度在布尔函数简洁表示中的作用，并推出了相应结论。该结论表明，丛图宽度对于表示布尔函数并不比树宽更加 “强大”，并且演示了该结论在知识编译中的应用。同时提出了一种可行的算法，能够将丛图宽度小于等于 k 的布尔电路编译成大小为 $O (9^{18k} k^2|Z|)$，执行时间也相同的分解否定标准式 (DNNF)。

    Mar, 2013

  • 小树幅线性规划的近线性时间算法：健壮中心路径的多尺度表示

    本文提出了一种基于内点法和树分解的线性规划问题求解算法，可以在近似相对误差为 ε 的情况下，在时间复杂度 Θ(n ⋅ tw² ⋅ log (1/ε)) 内求解给定的线性规划问题，其中 tw 是输入图的树宽，并且是第一个时间复杂度与子问题 Ax=b 的最快时间复杂度相匹配的算法。

    Nov, 2020

  • 超树分解与可处理查询

    本文研究了关于合取查询 (conjunctive queries) 的一些决策问题，发现针对无环或几乎无环查询的问题虽然一般来说是 NP 完全，但限制到这些查询中节点的树宽度和循环度是有界的，变得易于处理。针对查询的宽度这一最普遍的概念，我们证明没有多项式时间的算法可以高效地判断查询的宽度是否小于等于 k，而引入的超树分解概念和超树宽度则可以周旋这一难点，使得相应的问题变得可解。

    Dec, 1998

  • 关于不冗余传播完备 CNF 公式的大小

    我们研究了对称正定 Horn 函数的传播完备（PC）CNF 公式，并证明了这些公式的最小大小与特定的覆盖数密切相关，即适当的 k 下的 n 元集合的 k 个子集最小覆盖所有 (k-1) 个子集。因此，我们证明了一个不冗余的 PC 公式，其大小比相同函数的最小 PC 公式的大小大一个因子 ϴ(n/ln n)。这补充了该因子已知的多项式上界。

    Sep, 2023

  • 深度为二和三的阈值电路的超线性门和超二次线性电缆下界

    该论文研究了神经计算的权限，并证明了阈值电路的下限

    Nov, 2015

  • QBF 作为 Courcelle 定理的替代

    本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法，研究人工智能领域的几个已知问题，其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性，但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。

    May, 2018

  • 从基于宽度的模型检查到基于宽度的自动定理证明

    该研究提出了一种通用框架，将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法，并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法，时间为 $ k^{O (1)}$ 双指数级。

    May, 2022

  • 通过收缩张量网络模拟量子计算

    本文证明了：如果基于一颗 treewidth 为 d 的图的量子电路中，其门控运算的总数为 T，则这个电路可以在 T^{O (1)}*exp [O (d)] 的时间里被确定性模拟。此外，本文还证明了：在施加到附近量子比特的约束下，可以高效地模拟对数深度电路。同时，如果随机选择资源并且基于 treewidth 很小的图，则 Raussendorf 和 Briegel 的 one-way 量子计算方案可以有效地被模拟。

    Nov, 2005