Докажите, что логическая функция, вычисляемая в T (n) на машине с ОЗУ, находится в DTIME (T (n) ^ 2)

Вопрос в упражнении 1.9 из книги Арора-Барака « Вычислительная сложность - современный подход» :

Определите машину Тьюринга в ОЗУ как машину Тьюринга с оперативной памятью. Мы формализуем это следующим образом: У машины есть бесконечный массив A, который инициализируется для всех пробелов. Он обращается к этому массиву следующим образом. Одна из рабочих лент машины обозначена как адресная лента. Также машина имеет два специальных алфавитных символа, обозначаемых R и W, и дополнительное состояние, которое мы обозначаем q_access. Всякий раз, когда машина входит в q_access, если ее адресная лента содержит 'i'R (где' i 'обозначает двоичное представление i), тогда значение A [i] записывается в ячейку рядом с символом R. Если его лента содержит 'i'Wa (где a - некоторый символ в машинном алфавите), тогда A [i] устанавливается в значение a.

Покажите, что если булева функция вычислима в течение времени (в течение некоторого времени может быть построена ) с помощью RAM TM, то она находится в . $f$ $T(n)$ $T$ $\mathrm{DTIME}(T(n)^2)$

Тривиальное решение с использованием дополнительных пар записи на магнитную ленту (адрес, значение) оказывается в , поскольку эта лента может иметь размер с пар, в то время как адрес каждой пары может иметь размер . $\mathrm{DTIME}(T(n)^3)$ $O(T(n)^2)$ $O(T(n))$ $O(T(n))$

complexity-theory turing-machines machine-models simulation куб.см
источник

2^{2^{T (n)}}

$2^{2^{T(n)}}$

T (n)

$T(n)$

\log (T (n))

$\log\left(T(n)\right)$

T (n)

$T(n)$

T (n)

$T(n)$

O (T (n))

$O(T(n))$

O (2^{T (n)})

$O(2^{T(n)})$

Обратите внимание, что Арора и Барак явно просят во введении другие не опубликованные ответы на свои вопросы. См. Также правила о домашних заданиях .

Каве

O (T (n)^{2})

$O(T(n)^2)$

Вы можете найти больше в первой главе справочника теоретической информатики.

Каве

Вы пишете в комментариях :

$T(n)$ $O(T(n))$

Можете ли вы использовать аналогичный аргумент для улучшения границ

$O(T(n)^2)$ $O(T(n))$ $O(T(n))$

Вы упоминаете в вопросе? Возможно, вам придется помнить, какие операции возможны в постоянном времени в ОЗУ, то есть с использованием точного определения, которое используют авторы.

Рафаэль
источник

Я надеюсь, что этот намек достаточно расплывчат, чтобы уважать пожелания авторов книги, но также несколько полезен (Эвристика: я бы сказал студенту столько же, если бы задача была задана как упражнение. Хотя, вероятно, не на экзамене.)

Рафаэль

Докажите, что логическая функция, вычисляемая в T (n) на машине с ОЗУ, находится в DTIME (T (n) ^ 2)

Ответы: