Почему эта функция вычислима в

10

Мой учебник гласит: «Мы определяем функцию следующим образом: f ( 1 ) = 2 и f ( i + 1 ) = 2 f ( i ) 1.2 . Обратите внимание, что при заданном n мы легко можем найти в O ( n 1.5 ) умножить число i так , чтобы n зажалось между f ( i ) и f ( i + 1)f:NNf(1)=2f(i+1)=2f(i)1.2nO(n1.5)inf(i) . "f(i+1)

Как я могу убедить себя, что на самом деле мы можем легко найти за O ( n 1,5 ) времени? Поскольку f определяется рекурсивно, я думаю, что мы должны вычислить f ( 1 ) , f ( 2 ) , f ( 3 ) f ( j ), пока f ( j ) n . Чтобы выяснить, сколько времени занимают эти вычисления, я думаю, что мы должны найти подходящую верхнюю границу для i, зависящую от n.iO(n1.5)ff(1),f(2),f(3)f(j)f(j)ninи мы должны найти верхнюю границу времени выполнения функции x2x1.2 . В конце концов, мы можем показать цитируемое предложение. К сожалению, я не вижу ни того, ни другого.

Я забыл упомянуть: пожалуйста, обратите внимание, что мы находимся в недетерминированном контексте. Таким образом, считается вычислимым в O ( п 1,5f с помощью недетерминированной машины Тьюринга.O(n1.5)


Поскольку довольно многие люди уже читали этот вопрос, причем некоторые из них сочли его полезным и интересным, но пока никто не ответил, я хочу предоставить дополнительную информацию о контексте: цитируемое утверждение является неотъемлемой частью доказательства теорема недетерминированной временной иерархии. Доказательство (с заявлением) можно найти, например, в книге Ароры и Барака , но я также нашел в Интернете немало других ресурсов, которые представляют такое же доказательство. Каждый из них называет утверждение простым или тривиальным и не раскрывает, как найти за O ( n 1,5 ) времени. Таким образом, либо все эти ресурсы, только что скопированные с Ароры и Барака, либо заявление на самом деле не так уж сложно.iO(n1.5)

user1494080
источник
1
Это похоже на доказательство теоремы недетерминированной иерархии времени в Arora & Barak, не так ли? Если так, я предполагаю, что недетерминизм играет здесь роль.
Г. Бах
Вы правы. Извините за это, я должен был упомянуть недетерминированный контекст. Не могли бы вы объяснить более подробно, как недетерминизм помогает нам показать границу O (n ^ 1.5)?
user1494080

Ответы:

4

Обозначим через длина числа x , т.е. log 2 x + 1 (для x > 0 ). Для вычисления 2 x требуется время O ( x ) в модели ОЗУ, поэтому для вычисления f ( i + 1 ) из f ( i ) требуется время O ( f ( i ) 1.2 ) = O ( | f|Икс|Иксжурнал2Икс+1Икс>02ИксО(Икс)е(я+1)е(я). Поэтому общее время работы . Поскольку f ( i ) растет быстрее, чем геометрически, общее время для вычисления f ( i + 1 ) равно O ( | f ( i + 1 ) | ) . Как вы указали, вы должны делать это до тех пор, пока f ( i + 1 ) n , что означает, что f ( i ) < n O ( | f (O(f(i)1.2)=O(|f(i+1)|)f(i)f(i+1)O(|f(i+1)|)f(i+1)nf(i)<n .O(|f(i+1)|)=O(f(i)1.2)=O(n1.2)

В модели машины Тьюринга с одной лентой для вычисления требуется время O ( x log x ) , поэтому общее время работы составляет O ( n 1,2 log n ) = O ( n 1,5 ) . Алгоритм вычисления 2 x заменяет [ x ] на 1 [ [ x ] ] (здесь [ x ] - двоичное представление x , а [ [2xO(xlogx)O(n1.2logn)=O(n1.5)2x[x]1[[x]][x]x является двоичным представлением, использующим разные цифры 0 , 1 ), а затем многократно выполняет преобразование [ [ x ] ] 0 [ [ x - 1 ] ] , для которого требуется время O ( | x | ) = O ( журнал х ) .[[x]]0,1[[x]]0[[x1]]O(|x|)=O(logx)

Юваль Фильмус
источник
Отлично, спасибо! Еще один вопрос: разве мы не должны утверждать, что | f (i) | растет быстрее, чем геометрически, а не что f (i) растет быстрее, чем геометрически?
user1494080
Так как , это то же самое, но ты прав. Что мы действительно хотим, это j i | f ( j ) | = O ( | f ( i ) | ) . |f(i+1)|=f(i)1.2ji|f(j)|=O(|f(i)|)
Юваль Фильмус