Пространственная переменная иерархия

Благодаря Immerman и Szelepcsényi известно, что если (даже для непространственных конструктивных функций). ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ $f=\Omega(\log)$

В той же статье Иммерман заявляет, что переменная иерархия пространства журналов разрушается, это означает, что (определение ограниченной чередующейся машины Тьюринга и того, что иерархия может быть найдена в Википедии ). $\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$

Есть ли статья об иерархии переменных пространств для ? На прошлой неделе я попросил Иммермана, который не помнил, чтобы читал что-нибудь подобное. В английском я хотел бы знать, есть ли какое-либо письменное доказательство того, что использование любого языка, которое может быть решено машиной Тьюринга с чередованиями, также может быть определено недетерминированным механизмом Тьюринга с той же границей пространства. $f=\Omega(\log)$ $j$

Мой вопрос на самом деле о поиске ссылки, потому что я думаю, что выяснил доказательства; но я думаю, что это уже может быть известно.

Может быть, я должен заявить о двух основных проблемах. Во-первых, если , скажем, , то невозможно составить TM, чтобы получить TM, что мы могли бы сделать с TM. Во-вторых, есть один аргумент для случая $f=O(n)$ $f=\log^2$ $SPACE(f)$ $SPACE(f)$ $\rm{LOGSPACE}$ $f=O(n)$ и один для но есть еще некоторая проблема для функции, которые не являются ни ни . $f=\Omega(n)$ $O(n)$ $\Omega(n)$

cc.complexity-theory reference-request space-bounded alternating-hierarchy Артур МИЛКИОР
источник

Было бы полезно, если бы вы могли включить краткое определение двух упомянутых вами иерархий.

Робин Котари

отсутствует иерархия в иерархиях

Суреш Венкат

Я добавил ссылку для чередования и иерархий, ограниченных пробелами, и быстрое определение на английском языке того, что я хотел бы получить. Боюсь, что для оракула hiearchie правильное определение может быть слишком длинным и в любом случае бесполезным, поскольку этот класс равен недетерминированному пространству журналов.

Артур МИЛЬЧИОР

единственное число иерархий - это иерархия, кстати. Вы можете редактировать это?

Суреш Венкат

Ред. Боюсь, я никогда не обращал на это внимания.

Артур МИЛЬЧИОР

Ответы:

$ALTS$ $SPACE(a(n),s(n))$ $a(n)$ $s(n)$

$AC^1$ $ALT$ $SPACE(\log n, \log n)$

$ALTS$ $SPACE(a(n),\log n) \subseteq NSPACE(a(n) \log n)$

Райан Уильямс
источник

Спасибо; это кажется действительно многообещающим. Я просто понятия не имею, где начал искать такую статью. Доказательство не показалось мне тривиальным следствием, потому что, пусть M - это TM в ASPACE (f, 2), пусть M1 - экзистенциальная часть, а M2 - универсальная часть. Мы больше не можем рассматривать M2 как coSPACE (f) = SPACVE (f) TM, потому что мы должны взять вход M1 во входной ленте. Но да, безусловно, есть что-то, что можно сделать, используя непосредственное доказательство. Даже если бы я не выключил, используя число «a (n)» чередования.

Еще

$ALTSPACE(a(n),s(n))$ $NSPACE(a(n)s(n))$ $a(n)$ $s(n)$

Объединение этого с теоремой Савича дает следующие результаты:

$ALTSPACE(\log n, \log n)$ $SPACE((\log n)^4)$

Следствие: аналогично, язык, вычислимый в полиномиальном пространстве с полиномиальным числом чередований, находится в детерминированном полиномиальном пространстве.

$ALTSPACE$ $STA$

[B] Л. Берман, "Сложность логических теорий", Теоретическая информатика 11 (1980) 71-77.

Сэм Бусс
источник