归约

Reduction

Reduction (归约) 的概念在学习加密学时已经有了较为深入的接触;在这节课中再见面令我十分惊喜。这更证明了 reduction 这一概念的普适性与强大。

Def. Problem XX reduces to problem YY if you can use an algorithm that solves YY to help solve XX.

我们定义 cost of solving XX = total cost of solving YY + cost of reduction.

  • total cost of solving YY: perhaps many calls to YY on problems of different sizes.
  • cost of reduction: preprocessing and postprocessing.

举例来说,假设问题 XX 为 finding the median,问题 YY 为 sorting,那么解决问题 XX 的代价为 Nlog⁡NN\log N (cost of sorting) +1+1 (cost of reduction).

最常见的一种 reduction 关系是 linear-time reduction,它几乎涵盖了目前我们接触过的所有 reduction。

Def. Problem XX linear-time reduces to problem YY if XX can be solved with:

  • Linear number of standard computational steps.
  • Constant number of calls to YY.

Lower Bound Determination

linear-time reduction 关系能够帮助我们找出某些算法的 lower bounds;通常情况下这些算法的 lower bounds 难以进行证明。例如, How to convince yourself no linear-time convex hull algorithm exists?

  • [hard way] Long futile search for a linear-time algorithm.
  • [easy way] Linear-time reduction from sorting.

凸包问题能够线性归约到 sorting 问题,而我们知道任何 compare-based sorting algorithm 都需要至少 ∼Nlog⁡N\sim N\log{N} 次比较;由此能够断言凸包问题的 lower bound 同样为 Ω(Nlog⁡N)\Omega(N\log{N})。

Classifying Problems

根据问题的计算复杂度对其进行归类是 linear-time reduction 思想的另一个重要应用。具有相同计算复杂度 (computational complexity) 的问题集合属于同一个 complexity class。举例来说:

  • integer multiplication 与 integer division, integer square, and integer square root 问题属于同一个 complexity class,因为它们具有相同的复杂度 (order of growth: M(N)M(N) ).
  • matrix multiplication 与 matrix inversion, matrix determinant, system of linear equations, LU decomposition, and least squares 问题属于同一个 complexity class,因为它们具有相同的复杂度 (order of growth: MM(N)MM(N) )

那么我们如何使用 linear-time reduction 来证明问题 XX 与 YY 具有相同的复杂度呢?(Desiderata)

  • First show that problem XX linear-time reduces to YY.
  • Second, show that YY linear-time reduces to XX.
  • Conclude that XX and YY share the same complexity even if we don't know what it is.
CC BY-NC-SA 4.0
正在加载评论…