参数化问题的空间复杂度研究

### 参数化问题的空间复杂度研究 #### 1. 引言 在设计经典或参数化算法时，人们往往更关注问题的时间复杂度，而忽视了空间复杂度。然而，对对数空间等空间类的研究是经典复杂性理论的重要组成部分。许多自然问题，如可达性、距离问题或强大逻辑的可满足性问题，并非是时间类（如 P 或 NP）的完全问题，而是空间类（如 L、NL 或 PSPACE）的完全问题。 由此推测，一些参数化问题可能不是标准参数化时间类（如 FPT、W[1] 或 XP）的完全问题，而是参数化空间类的完全问题。并且，根据经典复杂性理论的研究结果，低空间复杂度的参数化问题可能可以快速求解。例如，参数化顶点覆盖问题空间复杂度较低，属于 para - L 类，在参数化环境中可以快速求解。 本文将研究一些自然参数化问题的空间复杂度，这些问题的空间复杂度此前尚未被深入研究。我们将探讨这些问题空间复杂度的差异，解释为何它们难以被证明为标准参数化时间类的完全问题，以及为何即使它们属于相同的参数化时间类，在实际求解速度上仍存在差异。我们将以有向和无向反馈顶点集问题以及树宽问题为例进行分析。 此前对参数化空间复杂度的研究主要集中在 para - P（即 FPT）的对数空间类似物 para - L 和 para - NL，以及 XP 的对数空间类似物 XL 和 XNL。但这些空间类不足以全面描述参数化世界的复杂性，因此我们将引入由参数化可达性问题激发的新类。 #### 2. 预备知识 - **参数化问题**：参数化问题是一个二元组 (Q, κ)，其中 Q 是一个语言，κ 是一个参数化函数，将输入实例映射到自然数（参数值）。本文要求参数的二进制表示可以在对数空间内计算，例如参数在输入中明确指定时就满足这一条件。 - **para - 类**：对于经典复杂度类 C，参数化问题 (Q, κ) 属于 para - C 类，如果存在一个字母表 Π、一个可计算函数 π: N → Π∗，以及一个语言 A ⊆ Σ∗ × Π∗，且 A ∈ C，使得对于所有 x ∈ Σ∗，有 x ∈ Q ⇐⇒ (x, π(κ(x))) ∈ A。特别地，FPT 等同于 para - P，所有固定参数可处理问题在对参数进行预计算后都属于 P。类似地，可以定义 para - L 和 para - NL 类，分别表示在对参数进行预计算后属于 L 和 NL 的问题。用 O 表示法，参数化问题 (Q, κ) 属于 para - L 类，如果存在一个函数 f: N → N，使得判定 x ∈ Q 的问题可以在空间 f(κ(x)) + O(log |x|) 内完成。 - **X - 类**：另一种定义参数化版本经典复杂度类 C 的方法是考虑其 X - 类。问题 (Q, κ) 属于 XC 类，如果对于每个自然数 w，切片 Qw = { x | x ∈ Q 且 κ(x) = w } 都属于 C。根据定义，显然有 para - C ⊆ XC。XP 类在参数化复杂性理论中广泛使用，对数空间类 XL 和 XNL 此前也有研究。 - **参数化归约**：为了比较参数化问题的复杂度，我们使用参数化对数空间归约（para - L - 归约）。设 (Q1, κ1) 和 (Q2, κ2) 是两个参数化问题，para - L - 归约是一个映射 R: Σ∗1 → Σ∗2，满足以下条件： 1. 对于所有 x ∈ Σ∗1，有 x ∈ Q1 ⇐⇒ R(x) ∈ Q2。 2. 存在一个可计算函数 g，使得 κ2(R(x)) ≤ g(κ1(x))。 3. R 相对于 κ1 是 para - L 可计算的。 所有本文涉及的类在 para - L - 归约下都是封闭的。 #### 3. 可处理问题的空间复杂度 从经典 fpt - 理论的角度来看，一旦一个参数化问题被证明可以在时间 f(κ(x)) · nc 内求解，其复杂度在原则上就“确定”了，后续研究主要集中在使 f 函数增长尽可能缓慢。本文将尝试通过研究问题的不同空间复杂度来区分 para - P 类中的问题。 ##### 3.1 距离问题 我们从一个看似简单的问题开始，即距离问题（p - distance）： - **实例**：一个有向图 G、图 G 中的两个顶点 s 和 t，以及一个自然数 l。 - **参数**：l。 - **问题**：在图 G 中是否存在一条从 s 到 t 的长度至多为 l 的路径？ 这个问题显然属于 para - P 类，由于距离问题属于 NL 类，所以它也属于 para - NL 类。它似乎是 para - NL 完全问题的一个很好候选。然而，之前关于 para - P、para - NL 和 para - L 类的研究表明，在考虑平凡参数化时，底层经典复杂度类的完全问题总是参数化版本的完全问题，但这一结论不适用于上