Решение задачи таково, что любой алгоритм допускает экспоненциально более быстрый алгоритм

19

В Алгоритмике Хромковича для сложных задач (2-е издание) есть эта теорема (2.3.3.3, стр. 117):

Существует (разрешимая) задача решения такая, что для каждого алгоритма A, который решает P, существует другой алгоритм A ′, который также решает P и дополнительно выполняетPAPAP
nN.TimeA(n)=log2TimeA(n)

является в худшем случае время выполненияАна входах размерапи средствами «для всехкроме конечного числа».TimeA(n)An

Доказательства не приводятся, и мы не знаем, как это сделать; это довольно нелогично, на самом деле. Как теорема может быть доказана?

Рафаэль
источник
1
Для заголовка может быть что-то вроде: «Есть ли проблема решения, для которой можно улучшить любой алгоритм решения?» При этом, это всего лишь выстрел в темноте, но не может ли быть так, что это вырожденный случай для тривиальной проблемы решения? Каким-то образом, если вы перевернете равенство, это означает, что всегда можно решить проблему «наихудшим» способом (делая бесполезные шаги). Но это только предположение.
Чарльз

Ответы: