LOGLOG = NLOGLOG?

Определите LOGLOG как класс языков, которые можно вычислить в пространстве O (loglog n) с помощью детерминированной машины Тьюринга (с двусторонним доступом к входу). Аналогично определите NLOGLOG как класс языков, которые могут быть вычислены в пространстве O (log log n) недетерминированной машиной Тьюринга (с двусторонним доступом к входу). Неужели не известно, что эти классы отличаются?

Я мог найти только некоторые более ранние обзоры и теорему, что если они равны, то L = NL (что не просто тривиальный аргумент заполнения!), Но почему-то я чувствую, что разделение этих классов не может быть таким сложным. Конечно, я могу быть совершенно неправ, но если каждый второй бит ввода представляет собой числа от 1 до n в порядке возрастания в двоичном, разделенном некоторыми символами, то машины уже могут узнать loglog n, и с каждым вторым битом мы можем введите проблему, которая может обмануть детерминистскую машину, но не недетерминированную. Я пока не понимаю, как именно это можно сделать, но похоже на возможный подход, так как с помощью этого трюка мы можем в основном вводить двоичное дерево глубины log n вместе с его структурой вместо обычной линейной ленты.

cc.complexity-theory reference-request space-bounded domotorp
источник

В результате быстрого поиска я обнаружил статью «Вычисления с сублогарифмическим пространством» Мацея Лискевича и Рудигера Рейщука. Также кажется, что в сублогарифмическом пространстве классовые отношения сильно зависят от используемой модели.

Chazisop

@chazisop: это один из опросов, которые я также нашел, кажется, что по этой теме все, по крайней мере, десять лет.

Домоторп

Я думаю, что @Kaveh упоминается в этом посте .

Сянь-Чжи Чанг 張顯之

Ваша память действительно расплывчата, теорема в том, что любая ТМ, использующая пространство o (log log n), должна быть регулярной.

Domotorp

@domotorp: оба утверждения являются теоремами, но для

вам нужна одиночная лента. (Конечно, для

вы также можете использовать одну ленту, поскольку перевод с одной ленты на другую не увеличивает места.) Ссылка, которую искал Нил Янг это: Кобаяши (1985) ( dx.doi.org/10.1016/0304-3975(85)90165-3 ) здание Хенни (1965) ( dx.doi.org/10.1016/S0019-9958(65)90399-2 ), который показал, что линейно-временные одноленточные ТМ выбирают только обычные языки и ввели последовательности пересечения.

o (n \log n)

$o(n \log n)$

S P A C E (o (\log \log n))

$SPACE(o(\log \log n))$

Джошуа Грохов

Ответы:

Запись в зоопарке сложности удивительно подробно; он утверждает, что NLOGLOG = co-NLOGLOG в статье

Недетерминированные вычисления в сублогарифмическом пространстве и пространственной конструктивности , Вильям Гефферт, SIAM Journal of Computing, 1991.

Но после краткого прочтения я не вижу никаких утверждений о том, что NLOGLOG закрыт в дополнение; может быть, нужен более глубокий взгляд. И главный результат у них есть, что нет недетерминирован полностью пространственно-конструктивны неограниченных монотонно возрастает функцию для . Известно, что если такие функции существуют, то $s(n)$ $s(n) = o(\log n)$

. $\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$

И в заключение автор заявил, что «... эта главная проблема разделения остается открытой ».

Как сказал @chazisop, отношения этих классов сложности низкого уровня зависят от моделей, и в записи зоопарка сказано, что

«Существует несколько возможных определений этого класса; наиболее распространенным является класс языков, которые могут быть вычислены в пространстве O (log log n) с помощью детерминированной машины Тьюринга с двусторонним доступом к входным данным».

Что совпадает с вашим определением, а также с документом.

Сянь-Чжи Чан 張顯之
источник

Я думаю, что это только претензии NLOGLOG = co-NLOGLOG. Я также не смог найти это утверждение в реферате статьи, хотя не смог открыть полный текст статьи.

domotorp

@domotorp: Вы правы. Я чувствую себя действительно неловко из-за моего неправильного ответа ... Я слишком устал, даже неправильно прочитал предложения, Может быть, я должен сделать перерыв на Рождество.

Сянь-Чи Чанг 之之