Симметрична машина Тьюринга является машиной Тьюринга , которая имеет конфигурацию граф , который неориентированный (то есть, конфигурация даю конфигурации я J тогда и только тогда , когда J выходов I).
Определение симметричных машин Тьюринга [ править ]
Формально мы определяем вариант машин Тьюринга с набором переходов вида (p, ab, D, cd, q) , где p, q - состояния, ab, cd - пары символов, а D - направление. Если D является влево , то голова машины в государственном р над символом ленты Ь предшествует символ а может быть переведена с помощью перемещения головки влево, изменяя состояние к ц и заменяя символ A, B на C, D . Всегда можно применить противоположный переход (q, cd, -D, ab, p) . Если DПравильно переход аналогичный. Возможность взглянуть на два символа и изменить оба одновременно несущественна, но упрощает определение.
Такие машины были впервые определены в 1982 году Гарри Р. Льюисом и Христосом Пападимитриу , [1] [2] , которые искали класс, в который можно было бы поместить USTCON. Проблема заключалась в том, что существует ли путь между двумя данными вершинами s, t неориентированный граф. До этого времени он мог быть размещен только в NL , несмотря на то, что, казалось, не требовал недетерминизма ( было известно, что асимметричный вариант STCON является полным для NL). Симметричные машины Тьюринга - это разновидность машин Тьюринга с ограниченной недетерминированной мощностью, и было показано, что они не менее мощны, чем детерминированные машины Тьюринга, что дает интересный промежуточный случай.
STIME (T (n)) - это класс языков, принятых симметричной машиной Тьюринга, работающей за время O (T (n)). Можно легко доказать, что STIME (T) = NTIME (T), ограничив недетерминизм любой машины в NTIME (T) начальным этапом, когда строка символов записывается недетерминированно, а затем следуют детерминированные вычисления.
SL = L [ редактировать ]
SSPACE (S (n)) - это класс языков, принимаемых симметричной машиной Тьюринга, работающей в пространстве O (S (n)) и SL = SSPACE (log (n)).
SL можно эквивалентно определить как класс проблемных журналов, сводимых к USTCON. Льюис и Пападимитриу по своему определению показали это, построив недетерминированную машину для USTCON со свойствами, которые, как они показали, достаточны для создания эквивалентной симметричной машины Тьюринга. Затем они заметили, что любой язык в SL является логопространством, сводимым к USTCON, поскольку из свойств симметричного вычисления мы можем рассматривать специальную конфигурацию как неориентированные ребра графа.
В 2004 году Омер Рейнгольд доказал, что SL = L, показав детерминированный алгоритм для USTCON, работающий в логарифмическом пространстве [3], за что он получил премию Грейс Мюррей Хоппер в 2005 году и (вместе с Ави Вигдерсон и Салил Вадхан ) премию Геделя 2009 года . Доказательство использует зигзагообразное произведение для эффективного построения расширительных графов .
Заметки [ править ]
- ^ Джеспер Янссон. Детерминированные алгоритмы связности графов с ограниченным пространством . Рукопись. 1998 г.
- ^ Гарри Р. Льюис и Христос Х. Пападимитриу. Симметричные вычисления в ограниченном пространстве. Теоретическая информатика . С. 161-187. 1982 г.
- ^ Рейнгольд, Омер (2008), "неориентированный подключения в лог-пространстве", Журнал ACM , 55 (4): 1-24, DOI : 10,1145 / 1391289,1391291 , MR 2445014 , ECCC TR04-094
Ссылки [ править ]
- Лекционные заметки: CS369E: Расширения в области компьютерных наук Синтия Дворк и Прахлад Харша
- Конспект лекций
- Конспект лекции Шэрон Брукнер
- Детерминированные пространственно-ограниченные алгоритмы связности графов Джеспер Янсон
