如何证明一个问题在一定时间复杂度下无解？

Question

在与我的教授讨论n x n 矩阵问题中的局部最小值时，他建议该问题存在一个具有

O(log n)

时间复杂度的解决方案。现在，我相当确定他是错的，尽管我不确定如何证明这种算法不存在。我将不胜感激任何可以用来证明在

O(log n)

时间内解决这个特定问题的可能性的见解或方法。

此外，这让我想到了一个更普遍的问题：

如何证明一个问题在给定的时间复杂度内无法解决？

谢谢！

Answer 1

提供了解决局部最小值问题的算法，我们可以编写一个对抗性算法来观察其操作，并在求解器查看每个矩阵单元之前确定它的值。

由于对手所做的分配代表了可以在开始时提供给求解器的有效输入，如果对手总是可以迫使求解器在证明局部性之前检查超过 Ω(log n) 个单元最小值，则证明在最坏情况下找到局部最小值必须花费超过 Ω(log n) 的时间。

鉴于求解器无法证明局部最小值，只要它检查过的每个单元都有一个更小的或未经检查的邻居，这样的对手可以按如下方式工作。

就在求解器检查尚未分配值的单元格（未分配的单元格）之前：

1. 如果新分配将其未分配单元格的连续区域划分为 2 个或更多部分，则选择这些部分中的“最大”部分以保持未分配状态。 其他部分填充的值低于迄今为止使用的所有值，并且值随着它们与新单元格的距离的增加而增加，因此只有新单元格可能成为局部最小值。 请注意，它将在所选区域中留下未分配的邻居，因此它不是可证明的最小值。 否则，新单元不会划分未分配单元的区域——它要么位于该区域的边界上，要么位于中间的一个岛上。 它被分配的值低于之前使用的所有值。 如果单元格完全被分配的单元格包围，这只能引入可证明的最小值。
请注意，通过条件（1），对手始终保持所有未分配单元格都连接的不变量。

为了证明最小值，求解器必须继续进行，直到连接单元的区域达到大小 1，并且求解器将其填充。

但是，如果我们考虑求解器

尚未检查的

单元格的连通区域，我们会发现每个这样的区域必须是对手在条件（1）中“未”选择的连通区域之一的一部分，因为这些是唯一未被检查的细胞。 由于对手总是选择最大的区域来维护，因此每个未选择的区域的大小为 2/2。

如果我们填充求解器检查的单元格，那么，在 n< n² 单元格的完整矩阵内，它只会留下大小为

2

/2 的区域未填充。 由于您需要填充至少 n 个单元格才能做到这一点（最佳方法是在中间画一条线），因此求解器必须检查至少 n 个单元格，并且不可能证明小于 Ω 的最小值(n) 时间。< n