一种基于简单包含-排除法的算法，用于(k, n)-MLC及相关问题

《ACM Transactions on Computation Theory》：A Simple Inclusion-Exclusion Based Algorithm for (k, n)-MLC and Related Problems

提出基于包含排除原理的多线性单项式系数和计算算法，时间复杂度为O(n^{k/2}·2^{O(k)}·s^{O(1)})，适用于任意域，通过引入非多线性补问题简化实现，并应用于r-简单k-路径问题计数。

　　

摘要

我们提出了一种基于包含排除原理的简单算法，用于计算由算术电路在任何域上计算出的多项式中所有多线性单项式系数的总和。该问题正式表示为（k, n）-MLC，定义如下：

•

给定一个计算齐次多项式的算术电路，其中该多项式的次数为 k，系数由 $F$ 表示，计算多项式 f 中所有多线性单项式系数的总和。

我们为（k, n）-MLC 问题提供了一种确定性算法，其运行时间为 O(n^k/2 · 2^O(k) · s^O(1)，其中 s 是电路的大小。我们的算法也在多项式空间上是有限的。（k, n）-MLC 问题最初由 Koutis 和 Williams [15, 17, 22] 研究，后来由 Arvind 等人 [3] 进一步研究，他们得到了一个运行时间为 $f$ 的算法。这里 $F$ 是任意域。

我们为（k, n）-MLC 问题提供了一种确定性算法，其运行时间为 O(n^k/2 · 2^O(k) · s^O(1)，其中 s 是电路的大小。Koutis 和 Williams [15, 17, 22] 首次研究了（k, n）-MLC 问题，后来 Arvind 等人 [3] 又得到了一个运行时间为 的算法，该算法使用了多项式的 Hadamard 乘积。Pratt [18] 提出了一种运行时间为 O^*(n^k/2) 的确定性算法，但这种方法依赖于有理数上对称多项式的非平凡 Waring 分解，而这不适用于小型有限域。

我们的方法以其简单性和对所有域的通用性而著称。与现有工作不同，我们引入了（k, n）-MLC 问题的补问题，我们称之为（k, n）-NMLC 问题。这种方法着眼于找到所有非多线性单项式系数的总和，这为我们提供了一种新的思考（k, n）-MLC 问题的方式。这种新方法导致了一个简单的算法，并有助于解释主导指数 k/2 的来源。

我们为（k, n）-NMLC 问题开发了一种确定性算法，其运行时间为 O(n^k/2 · 2^O(k) · s)，并且使用多项式空间。对于（k, n）-MLC 问题的算法非常直接：它从多项式中所有单项式系数的总和（包括多线性和非线性单项式）中减去所有非多线性单项式系数的总和（这是（k, n）-NMLC 问题的结果）。

我们应用这些结果得到了一个确定性算法，用于精确计算 [1, 13] 中引入的 r-简单 k-路径问题，并且还用于（k, n）-MLC 问题的一个推广，我们称之为（r, k, n）-MLC 问题。这涉及计算由给定算术电路产生的多项式中所有单项式系数的总和，其中每个变量的次数最多为 r。