Л/поли
В сложности вычислений теории L/poly — это класс сложности логарифмических космических машин с полиномиальным количеством советов . L/poly — это класс неоднородного логарифмического пространства, аналогичный классу неоднородного полиномиального времени P/poly . [1]
Формально, чтобы формальный язык L принадлежал L/poly, должна существовать рекомендующая функция f , которая отображает целое число n в строку полиномиальной длины от n , и машина Тьюринга M с двумя входными лентами только для чтения и одной считывающей лентой. -записать ленту логарифмического размера входного сигнала, такую, что входной сигнал x длины n принадлежит L тогда и только тогда, когда машина M принимает входные данные x , f ( n ) . [2] Альтернативно и более просто, L находится в L/poly тогда и только тогда, когда его можно распознать ветвящимися программами полиномиального размера. [3] Одним из направлений доказательства того, что эти две модели вычислений эквивалентны по мощности, является наблюдение, что, если существует программа ветвления полиномиального размера, ее можно задать с помощью рекомендательной функции и смоделировать с помощью машины Тьюринга. В другом направлении машина Тьюринга с логарифмическим пространством записи и полиномиальной лентой советов может быть смоделирована с помощью ветвящейся программы, состояния которой представляют собой комбинацию конфигурации записываемой ленты и положения головок машины Тьюринга на двух других. ленты.
В 1979 году Алелиунас и др. показал, что симметричное логпространство содержится в L/poly. [4] Однако этот результат был заменен результатом Омера Рейнгольда о том, что SL сжимается до однородного лог-пространства. [5]
BPL содержится в L/poly, который является вариантом теоремы Адлемана . [6]
Ссылки
[ редактировать ]- ^ Зоопарк сложности : L/poly .
- ^ Тирауф, Томас (2000), Вычислительная сложность проблем эквивалентности и изоморфизма , Конспект лекций по информатике, том. 1852, Шпрингер-Верлаг, с. 66, ISBN 978-3-540-41032-4 .
- ^ Кобэм, Алан (1966), «Проблема распознавания множества идеальных квадратов», Труды 7-го ежегодного симпозиума IEEE по теории коммутации и автоматов (SWAT 1966) , стр. 78–87, doi : 10.1109/SWAT.1966.30 .
- ^ Алелиюнас, Ромас; Карп, Ричард М .; Липтон, Ричард Дж .; Ловас, Ласло ; Ракофф, Чарльз (1979), «Случайные блуждания, универсальные последовательности обхода и сложность задач лабиринта», Труды 20-го ежегодного симпозиума по основам информатики , Нью-Йорк: IEEE, стр. 218–223, doi : 10.1109/SFCS .1979.34 , МР 0598110 .
- ^ Рейнгольд, Омер (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291 , MR 2445014 .
- ^ Нисан, Ноам (1993), «Однократное чтение и множественный доступ к случайности в пространстве журналов», Theoretical Computer Science , 107 (1): 135–144, doi : 10.1016/0304-3975(93)90258-U , MR 1201169 .