如何证明问题无法在指定时间复杂度内求解？附矩阵问题示例

首先明确局部最小值的定义：矩阵中的一个元素，若为内部元素则比上下左右四个相邻元素都小；若为边界元素则比所有存在的相邻元素都小。

为什么O(log n)的解法不可能？核心原因在于输入规模与算法能获取的信息量不匹配：

• n×n矩阵共有n²个元素，而O(log n)时间的算法最多只能读取或处理O(log n)个元素，这远小于矩阵的总元素数。
• 用对手论证可以直观说明：假设某个算法声称能在O(log n)时间内找到局部最小值，我们可以构造一个“对手”，它会根据算法每一步读取的元素动态调整矩阵的其他元素：
  1. 对于算法已经读取的元素，让它们的所有相邻元素都比自身小（这样这些元素肯定不是局部最小值）；
  2. 在算法从未读取过的区域，设置一个真正的局部最小值。
• 由于算法只读取了O(log n)个元素，未读取的区域必然存在（当n足够大时），算法无法感知到这个局部最小值的存在，最终只能输出错误结果。

另外从信息论角度看：要确定一个局部最小值，至少需要排除Ω(n)个不可能的位置，而每个操作最多只能排除常数个位置，因此算法的时间复杂度至少是Ω(n)，远高于O(log n)。

以下是几种常用的方法：

• 信息论下界法：计算问题需要区分的输入或解的数量，每个计算步骤（比如一次比较、一次元素读取）只能获取有限的信息量。比如排序问题，有n!种可能的排列，每次比较只能将可能的排列数减半，因此至少需要log₂(n!)=Ω(n log n)次比较，这就是排序的下界。
• 对手论证法：构造一个动态生成输入的“对手”，它会根据算法的每一步操作调整输入，迫使算法必须执行足够多的步骤才能得到正确结果。这种方法常用于构造性证明下界，比如前面矩阵局部最小值的例子。
• 归约法：将一个已知有严格时间下界的问题，归约到当前问题。如果问题X的下界是Ω(T(n))，且X可以在O(1)或远小于T(n)的时间内归约到问题Y，那么Y的下界至少是Ω(T(n))。比如如果能将排序问题归约到某个搜索问题，那么该搜索问题的下界至少是Ω(n log n)。
• 计数论证法：统计算法所有可能的执行路径数量，对比问题需要区分的输入数量。如果算法的路径数小于输入的区分需求，说明必然有不同输入对应同一条路径，算法无法正确处理，因此需要更多步骤。
• 利用已知计算模型下界：不同的计算模型（比如比较模型、RAM模型）有不同的下界结论。比如在比较模型下，很多搜索、排序类问题的下界已经被证明，可以直接引用。

内容的提问来源于stack exchange，提问作者Nik