LOGLOG = NLOGLOG?

32

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

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

domotorp
источник
3
В результате быстрого поиска я обнаружил статью «Вычисления с сублогарифмическим пространством» Мацея Лискевича и Рудигера Рейщука. Также кажется, что в сублогарифмическом пространстве классовые отношения сильно зависят от используемой модели.
Chazisop
1
@chazisop: это один из опросов, которые я также нашел, кажется, что по этой теме все, по крайней мере, десять лет.
Домоторп
1
Я думаю, что @Kaveh упоминается в этом посте .
Сянь-Чжи Чанг 張顯 之
2
Ваша память действительно расплывчата, теорема в том, что любая ТМ, использующая пространство o (log log n), должна быть регулярной.
Domotorp
4
@domotorp: оба утверждения являются теоремами, но для вам нужна одиночная лента. (Конечно, для S P A C E ( o ( log log n ) ) вы также можете использовать одну ленту, поскольку перевод с одной ленты на другую не увеличивает места.) Ссылка, которую искал Нил Янг это: Кобаяши (1985) ( dx.doi.org/10.1016/0304-3975(85)90165-3 ) здание Хенни (1965) ( dx.doi.org/10.1016/S0019-9958(65)90399-2 ), который показал, что линейно-временные одноленточные ТМ выбирают только обычные языки и ввели последовательности пересечения.о(NжурналN)SпAСЕ(о(журналжурналN))
Джошуа Грохов

Ответы:

15

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

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

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

.SпAСЕ[s(N)]NSпAСЕ[s(N)]

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

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

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

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

Сянь-Чжи Чан 張顯 之
источник
5
Я думаю, что это только претензии NLOGLOG = co-NLOGLOG. Я также не смог найти это утверждение в реферате статьи, хотя не смог открыть полный текст статьи.
domotorp
2
@domotorp: Вы правы. Я чувствую себя действительно неловко из-за моего неправильного ответа ... Я слишком устал, даже неправильно прочитал предложения, Может быть, я должен сделать перерыв на Рождество.
Сянь-Чи Чанг 之 之