В Алгоритмике Хромковича для сложных задач (2-е издание) есть эта теорема (2.3.3.3, стр. 117):
Существует (разрешимая) задача решения такая, что для каждого алгоритма A, который решает P, существует другой алгоритм A ′, который также решает P и дополнительно выполняет
является в худшем случае время выполненияАна входах размерапи ∀ ∞ средствами «для всехкроме конечного числа».
Доказательства не приводятся, и мы не знаем, как это сделать; это довольно нелогично, на самом деле. Как теорема может быть доказана?
complexity-theory
Рафаэль
источник
источник
Ответы:
Кажется, это простой случай теоремы Блума об ускорении :
источник