Временные иерархии в DSPACE (O (s (n)))

Теорема иерархии времени утверждает, что машины Тьюринга могут решить больше проблем, если у них есть (достаточно) больше времени. Имеет ли это какое-то значение, если пространство ограничено асимптотически? Как $\textrm{DTISP}(g(n), O(s(n)))$ относится к $\textrm{DTISP}(f(n), O(s(n)))$ если $\frac{f}{g}$ растет достаточно быстро?

Меня особенно интересует случай, когда $s(n) = n$ , $g(n) = n^3$ и $f(n) = 2^n$ .

В частности, я считал следующий язык: $L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w) \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps},$ $k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \}$

Однако $L_k$ может быть определено за $n^3$ шагов с использованием $(k+1)n \in O(n)$ пространства.

Не ограничивая $M$ четырьмя символами ленты и, таким образом, позволяя сжать $O(n)$ ячеек в $n$ ячеек, мы получаем проблемы с пространством при моделировании $M$ со слишком большим количеством символов на ленте. В этом случае язык больше не находится в $\text{DSPACE}(O(n))$ . То же самое происходит при установке $k = h(|w|)$ для некоторого $h$ который может быть вычислен достаточно быстро.

Этот вопрос в основном перефразирует мой вопрос здесь .

Редактировать резюме: Изменено $\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$ на $\textrm{DTISP}(f(n), s(n))$ , однако, я думаю, что пересечение также стоит подумать.

$\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$$\mathrm{NSPACE}(O(n))$$\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$

Однако при вероятных предположениях о сложности вычислений существует надлежащая иерархия. Например, если для каждого CIRCUIT-SAT ∉ io- , то где , равно , а - пространственно-временная конструкция.O ( 2 n - ε ) D T I S P ( O ( f ) , O ( s ( n ) ) ) ⊊ D T I S P ( O ( f 1 + ε ) , O ( s ( n ) ) ) f ( n ) ≥ n f ( $ε>0$$O(2^{n-ε})$$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
$f(n)≥n$$f(n)$$2^{o(\min(n,s(n)))}$$f$

В частности (в предположении), существование удовлетворяющего назначения для схем с входы и размер служит как контрпример к равенству классов.$⌊\mathrm{lg}(f^{1+ε/2})⌋$$(\log f)^{O(1)}$

Примечания:

• CIRCUIT-SAT, по крайней мере, такой же твердый, как -SAT (который используется в гипотезе сильного экспоненциального времени).$k$

• В соответствии с соглашением, в CIRCUIT-SAT, - количество входных проводов; размер схемы .$n$$n^{O(1)}$

• Если предположение использовало CIRCUIT-SAT для размеров квазилинейных цепей, то ограничение на может быть ослаблено до . Кроме того, более слабые / более сильные предположения о твердости CIRCUIT-SAT дают более слабые / более сильные иерархии (что мы можем доказать в настоящее время).$f(n)$$O((2-ε)^{\min(n,s(n))})$

• io означает бесконечно часто, и может быть отброшено для , которые в определенном смысле непрерывны (включая ).$f$$f(n)=n^a$

• Вероятно, что иерархия DTISP достаточно резкая, чтобы отличить от (и, возможно, ) (когда не слишком велико относительно разрешенного пространства).$O(f)$$o(f/\log f)$$o(f)$$f$

• Чтобы отличить от , нам нужно только более слабое предположение P ≠ PSPACE.$n^a$$2^n$