How to prove a problem is unsolvable in a certain Time Complexity?

Question

While discussing the Local Minimum in n x n Matrix Problem with my professor, he suggested that there exists a solution with O(log n) time complexity for this problem. Now, I'm fairly sure he is wrong, though I am uncertain of how to prove the non-existence of such algorithm. I would appreciate any insights or methodologies that can be used to demonstrate the impossibility of solving this specific problem in O(log n) time.

Also, this leads me to a more general question:

How can one prove that a problem cannot be solved within a given time complexity?

Thank you!

Answer 1

Provided with an algorithm that solves the local minimum problem, we can write an adversarial algorithm that observes its operation, and determines the value of each matrix cell just before the solver looks at it.

Since the assignments that the adversary makes represent a valid input that could have been provided to the solver at the beginning, if the adversary can always force the solver to examine more than Ω(log n) cells before it can prove a local minimum, then it proves that finding a local minimum must take at more than Ω(log n) time in the worst case.

Given that a solver cannot prove a local minimum as long as every cell it has examined has a smaller or unexamined neighbor, such an adversary can work as follows.

Just before the solver examines a cell that doesn't yet have an assigned value (an unassigned cell):

1. If the new assignment would partition its contiguous region of unassigned cells into 2 or more parts, then the largest of those parts is selected to remain unassigned. The other parts, along with the new cell, are filled with values that are lower than all values used so far, with values increasing as their distance from the new cell increases, so that only the new cell could possibly become a local minimum. Note that it will be left with an unassigned neighbor in the selected region, so it is not a provable minimum.
2. Otherwise, the new cell does not partition a region of unassigned cells -- it is either on the boundary of such a region, or an island in the middle. It is assigned a value that is lower than all values previously used. This could only introduce a provable minimum if the cell is completely surrounded by assigned cells.

Note that, via condition (1), the adversary always maintains the invariant that all of the unassigned cells are connected.

In order to prove a minimum, the solver must proceed until that region of connected cells gets to size 1, and the solver fills it in.

But then if we consider the connected regions of cells that the solver has not examined, we see that each such region must be part of one of the connected regions that was not selected by the adversary in condition (1), because those are the only cells that were not examined.

Since the adversary always selects the largest region to maintain, every unselected region has size < n²/2.

If we fill in the cells examined by the solver, then, it leaves only regions of size < n²/2 unfilled, within the full matrix of n² cells. Since you need to fill in at least n cells to do that (the optimal way is to just draw a line across the middle), the solver must have examined at least n cells, and could not possibly have proven a minimum in less than Ω(n) time.