Можно ли решить, является ли данный алгоритм асимптотически оптимальным?

Есть ли алгоритм для решения следующей задачи:

При заданной машине Тьюринга которая определяет язык L , существует ли машина Тьюринга M 2, решающая L так , что t 2 ( n ) = o ( t 1 ( n ) ) ?$M_1$$L$
$M_2$$L$$t_2(n) = o(t_1(n))$

Функции и t 2 являются наихудшим временем работы машин Тьюринга M 1 и M 2 соответственно.$t_1$$t_2$$M_1$$M_2$

А как насчет космической сложности?

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

Мы сводим проблему остановки на пустой ленте к вашей проблеме оптимальности времени выполнения.

Пусть - заданная машина Тьюринга. Пусть N будет следующей машиной Тьюринга:$M$

: на входе n 1. Запустите M на чистой ленте для (не более) n шагов. 2. Если M не останавливается за n шагов, запустите цикл размером 2 n , затем верните NO. 3. В противном случае верните ДА.$N$$n$
$M$$n$
$M$$n$$2^n$

Есть два случая:

1. Если не останавливается на пустой ленте, машина N будет работать на Θ ( 2 n ) шагов на входе n . Таким образом, его время работы составляет Θ ( 2 н ) . В этом случае N , очевидно, не является оптимальным.$M$$N$$\Theta(2^n)$$n$$\Theta(2^n)$$N$

2. Если останавливается на пустой ленте, то машина N будет работать с постоянным числом шагов для всех достаточно больших n , поэтому время работы O ( 1 ) . В этом случае N , очевидно, оптимально.$M$$N$$n$$O(1)$$N$

Короче говоря:

$M$$N$$N$$M$

Аналогичный аргумент можно использовать для пространства, т. Е. Также неразрешимо проверить, является ли данная машина Тьюринга оптимальной с точки зрения пространства, которое она использует.

Даже более сильное утверждение верно: мы не можем решить, является ли данная вычислимая функция верхней границей временной сложности вычисления данной вычислимой функции. Аналогично для космоса. Т.е. даже базовая теория сложности не может быть автоматизирована алгоритмами (что можно считать хорошей новостью для теоретиков сложности;).

Как уже упоминалось, ответ - нет.

Но есть интересная статья, написанная Блюмом " Машинно-независимая теория сложности рекурсивных функций ". Он показал, что есть некоторые функции, обладающие тем свойством, что независимо от того, насколько быстрой может быть программа для вычисления этих функций, существует другая программа для их вычисления намного быстрее .

очень хорошая собственность!

Ха! Если бы ответ был да, мы бы жили в другом мире.

$A_0$$A$$L$$A_0$$A$

К сожалению, это невозможно, и я лично считаю, что доказательство (нетривиальной) оптимальности является наиболее интересной (и сложной) проблемой в информатике. Насколько я знаю - я был бы рад исправить - нет результата оптимальности для любой полиномиальной задачи (кроме тривиальных результатов оптимальности курса алгоритмов, занимающих время, пропорциональное размеру входных данных).