Задача Дана машина Тьюринга которая знает время выполнения O ( g ( n ) ) относительно длины ввода n , является временем выполнения M ∈ O ( f ( n ) ) ?
Разрешима ли указанная выше проблема для некоторых нетривиальных пар и f ? Решение тривиально, если g ( n ) ∈ O ( f ( n ) ) .
Это связано с проблемой Разрешаемы ли границы времени выполнения в P? (ответ: нет) . Из ответа Виолы можно вывести , что если и f ( n ) ∉ O ( g ( n ) ), то проблема неразрешима.
Требование , что потому , что М ' в доказательство необходимости Виолы O ( п ) время , чтобы найти свой входной размер. Таким образом, доказательство Виолы не может работать, когда f ( n ) = 1 .
Было бы интересно, если бы мы могли выбрать время выполнения алгоритмов сублинейного времени. Особый случай - когда мы имеем произвольные и f ( n ) = 1 .
источник
Ответы:
Вот несколько замечаний, которые могут иметь отношение к теме:
источник