Если мы посмотрим на теорему об иерархии DTIME, то получим журнал из-за накладных расходов при моделировании детерминированной машины Тьюринга на универсальной машине: DTIME(flogf)⊊DTIME(f)DTIME(flogf)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) У нас нет такого рода накладных расходов на...
В одном предложении: подразумевает ли существование иерархии для какие-либо результаты дерандомизации?B P T I M EBPTIME\mathsf{BPTIME} но неопределенный вопрос: подразумевает ли существование иерархии для какие-либо трудные нижние границы? Влияет ли решение этой проблемы на известный барьер в...
Первоначальная теорема недетерминированной временной иерархии принадлежит Кук (ссылка на С. Кука, иерархия недетерминированной временной сложности , JCSS 7 343–353, 1973). Теорема утверждает, что для любых действительных чисел r1r1r_1 и r2r2r_2 , если 1≤r1<r21≤r1<r21 \le r_1 \lt r_2 то NTIME...
Верно ли, что в полиномиальной иерархии существуют проблемы, разрешимые во времени (с помощью чередующейся машины Тьюринга на некотором уровне полиномиальной иерархии), которые не разрешимы в O ( n k - 1 ) на любом уровне полиномиальная иерархия? Другими словами - существует ли теорема временной...
Определите как класс языков, которые могут быть приняты машиной (множественной) Тьюринга за время f ( n ) + 1 . (« + 1 » просто для упрощения обозначений и предотвращения путаницы.) Обратите внимание, что вокруг f ( n ) + 1 нет O ( ⋅ ) .D T I M E (f( н ) )DTяMЕ(е(N))\mathsf{DTIME}(f(n))е( n ) +...
Теорема иерархии времени утверждает, что машины Тьюринга могут решить больше проблем, если у них есть (достаточно) больше времени. Имеет ли это какое-то значение, если пространство ограничено асимптотически? Как DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) относится к...
Короче говоря, теоремы иерархии времени говорят о том, что машина Тьюринга может решить больше проблем, если у нее будет больше времени для вычислений. Подробно для детерминированных TM и функций, построенных по времени, с это и для недетерминированных функций TM и функций времени, f, g с f (n + 1)...