归约
Reduction
Reduction (归约) 的概念在学习加密学时已经有了较为深入的接触;在这节课中再见面令我十分惊喜。这更证明了 reduction 这一概念的普适性与强大。
Def. Problem
我们定义 cost of solving
- total cost of solving
: perhaps many calls to on problems of different sizes. - cost of reduction: preprocessing and postprocessing.
举例来说,假设问题
最常见的一种 reduction 关系是 linear-time reduction,它几乎涵盖了目前我们接触过的所有 reduction。
Def. Problem
- Linear number of standard computational steps.
- Constant number of calls to
.
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 都需要至少
Classifying Problems
根据问题的计算复杂度对其进行归类是 linear-time reduction 思想的另一个重要应用。具有相同计算复杂度 (computational complexity) 的问题集合属于同一个 complexity class。举例来说:
- integer multiplication 与 integer division, integer square, and integer square root 问题属于同一个 complexity class,因为它们具有相同的复杂度 (order of growth:
). - matrix multiplication 与 matrix inversion, matrix determinant, system of linear equations, LU decomposition, and least squares 问题属于同一个 complexity class,因为它们具有相同的复杂度 (order of growth:
)
那么我们如何使用 linear-time reduction 来证明问题
- First show that problem
linear-time reduces to . - Second, show that
linear-time reduces to . - Conclude that
and share the same complexity even if we don't know what it is.