Предположим, что существует детерминированный алгоритм, который работает за время

(быстрее чем за линейное время). Под детерминированным я понимаю алгоритм, который исполняется всякий раз одинаково, если получает на вход одни и те же входные данные. Пусть такой алгоритм проделал определённое число шагов, какой будет следующий шаг?
Для детерминированного алгоритма решающего нашу задачу, это зависит только от искомого числа

и тех ячеек

, которые он успел просмотреть до сих пор. Следовательно, если мы поменяем числа в ещё непросмотренных ячейках, то на выбор следующего шага алгоритма это не повлияет.
Если алгоритм работает за

, то можно выбрать такое большое

, что алгоритм совершит менее

обращений к матрице

.
Подадим на вход алгоритма число

и матрицу

такие, что
1.

должно быть достаточно велико, чтобы алгоритм просмотрел менее

элементов

2.
![$A[i][j] = i + j$ $A[i][j] = i + j$](https://dxdy-03.korotkov.co.uk/f/e/6/a/e6a6506c6352fe7b8802d53d14b82a8282.png)
вне побочной диагонали,
![$A[i][j] = i + j + 1$ $A[i][j] = i + j + 1$](https://dxdy-02.korotkov.co.uk/f/1/4/f/14f4c1a7d4a91f4e57cdd0b4da0fbece82.png)
на побочной диагонали (на ней

)
3.

Ясно, что

в

отсутствует. Алгоритм должен сказать "нет".
Запустим алгоритм, запишем все элементы к которым он обращался. Выберем непросмотренный элемент на побочной диагонали. В него впишем

, то есть, уменьшим на единицу. Назовём такую матрицу

.
Последовательность шагов детерминированного алгоритма для матриц

и

одинакова. Следовательно алгоритм и для матрицы

ответит "нет".
Мы доказали следующее утверждение: для любого детерминированного алгоритма со временем работы

можно предъявить матрицу на которой он ошибётся. Противоречие, таких алгоритмов не существует.