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

13

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

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

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

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

Может быть, я должен заявить о двух основных проблемах. Во-первых, если , скажем, f = log 2 , то невозможно составить S P A C E ( f ) TM, чтобы получить S P A C E ( f ) TM, что мы могли бы сделать с L O G S P A C E TM. Во-вторых, есть один аргумент для случая f = O ( n )f=O(n)f=log2SPACE(f)SPACE(f)LOGSPACEf=O(n)и один для но есть еще некоторая проблема для функции, которые не являются ни O ( n ), ни Ω ( n ) .f=Ω(n)O(n)Ω(n)

Артур МИЛКИОР
источник
2
Было бы полезно, если бы вы могли включить краткое определение двух упомянутых вами иерархий.
Робин Котари
отсутствует иерархия в иерархиях
Суреш Венкат
Я добавил ссылку для чередования и иерархий, ограниченных пробелами, и быстрое определение на английском языке того, что я хотел бы получить. Боюсь, что для оракула hiearchie правильное определение может быть слишком длинным и в любом случае бесполезным, поскольку этот класс равен недетерминированному пространству журналов.
Артур МИЛЬЧИОР
единственное число иерархий - это иерархия, кстати. Вы можете редактировать это?
Суреш Венкат
Ред. Боюсь, я никогда не обращал на это внимания.
Артур МИЛЬЧИОР

Ответы:

7

ALTSSPACE(a(n),s(n))a(n)s(n)

AC1ALTSPACE(logn,logn)

ALTSSPACE(a(n),logn)NSPACE(a(n)logn)

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

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

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

ALTSPACE(logn,logn)SPACE((logn)4)

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

ALTSPACESTA

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

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