Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории сложности вычислений , SL ( Симметричный Logspace или Sym-L ) является класс сложности проблем лога-пространство приводимого к USTCON ( неориентированного ул подключение ), который является проблемой определения того , существует ли путь между двумя вершинами в качестве неориентированного графа , иначе описывается как проблема определения, находятся ли две вершины в одном компоненте связности . Эта проблема также называется проблемой ненаправленной достижимости . Не имеет значения, сводимость многих единиц или сводимость по Тьюрингу.используется. Хотя эта эквивалентная формулировка первоначально описывалась в терминах симметричных машин Тьюринга , она очень сложна, и на практике используется определение сводимости.

USTCON - это частный случай STCON ( направленная достижимость ), проблема определения, существует ли направленный путь между двумя вершинами в ориентированном графе , что является полным для NL . Поскольку USTCON завершен в рамках SL , большинство достижений, влияющих на USTCON, также повлияли на SL . Таким образом, они связаны и обсуждаются вместе.

В октябре 2004 года Омер Рейнгольд показал , что SL = L .

Происхождение [ править ]

SL был впервые определен в 1982 году Гарри Р. Льюисом и Христосом Пападимитриу , [1] которые искали класс для размещения USTCON, который до этого времени мог, в лучшем случае, быть помещен только в NL , несмотря на то, что, казалось, не требовал недетерминизм. Они определили симметричную машину Тьюринга , использовали ее для определения SL, показали, что USTCON является полным для SL, и доказали, что

где L - более известный класс задач, решаемых с помощью обычной детерминированной машины Тьюринга в логарифмическом пространстве, а NL - класс задач, решаемых с помощью недетерминированных машин Тьюринга в логарифмическом пространстве. Результат Рейнгольда, обсуждаемый ниже, показывает, что на самом деле, когда оно ограничено логическим пространством, симметричная машина Тьюринга эквивалентна по мощности детерминированной машине Тьюринга.

Полные проблемы [ править ]

По определению, USTCON является полным для SL (все проблемы в SL сводятся к нему, включая его самого). Было обнаружено еще много интересных полных задач, большинство из которых было прямым или косвенным сокращением из USTCON, и их сборник был составлен Альваресом и Гринлоу. [2] Многие проблемы относятся к теории графов . Вот некоторые из наиболее простых и важных проблем SL-complete, которые они описывают:

  • USTCON
  • Моделирование симметричных машин Тьюринга: принимает ли СТМ заданный ввод в определенном пространстве, заданном в унарном формате?
  • Вершинно-непересекающиеся пути: существуют ли k путей между двумя вершинами, имеющих общие вершины только в конечных точках? (обобщение USTCON, эквивалентное вопросу, является ли граф k- связным)
  • Является ли данный граф двудольным графом или, что то же самое, имеет ли он раскраску в два цвета?
  • У двух неориентированных графов одинаковое количество компонент связности ?
  • Имеет ли граф четное число связных компонентов?
  • Для данного графа существует ли цикл, содержащий данное ребро?
  • У остовных лесов двух графов одинаковое количество ребер?
  • Для графа, все ребра которого имеют разные веса, является ли данное ребро остовным лесом минимального веса ?
  • Исключительная или 2- выполнимость : учитывая формулу , требующую , что х я XOR х J справедлива для числа пар переменных ( х я , х J ), есть присваивание переменных , что делает его истинным?

В комплементы всех этих проблем в SL , а также, поскольку, как мы увидим, SL закрывается под дополнением.

Из того факта, что L = SL , следует, что многие другие проблемы являются SL-полными по отношению к редукциям в лог-пространстве: каждая нетривиальная проблема в L или SL является SL- полной; более того, даже если редукции относятся к некоторому меньшему классу, чем L , L -полнота эквивалентна SL -полноте. В этом смысле этот класс стал несколько тривиальным.

Важные результаты [ править ]

Существуют хорошо известные классические алгоритмы , такие как поиска в глубину и поиск в ширину , которые решают USTCON в линейном времени и пространстве. Их существование, показали , задолго до того, SL была определена, доказывает , что SL содержится в P . Также нетрудно показать, что USTCON и, следовательно, SL находятся в NL , поскольку мы можем просто недетерминированно угадывать в каждой вершине, какую вершину посетить следующей, чтобы обнаружить путь, если он существует.

Однако первым нетривиальным результатом для SL была теорема Сэвича, доказанная в 1970 году, которая предоставила алгоритм, решающий USTCON в пространстве log 2 n . Однако, в отличие от поиска в глубину, этот алгоритм непрактичен для большинства приложений из-за его потенциально сверхполиномиального времени работы. Одним из следствий этого является то, что USTCON и, следовательно, SL находятся в DSPACE (log 2 n ). [3] (На самом деле теорема Сэвича дает более сильный результат, что NL находится в DSPACE (log 2 n ).)

Хотя в алгоритме Сэвича не было (единообразных) детерминированных пространственных улучшений в течение 22 лет, в 1979 году Алелиунасом и др. Был обнаружен весьма практичный вероятностный алгоритм лог-пространства: просто начните с одной вершины и выполните случайное блуждание, пока не найдете другую один (затем принять) или до тех пор, пока | V | 3 раза прошло (потом отклоняю). [4] Ложные отклонения выполняются с небольшой ограниченной вероятностью, которая экспоненциально уменьшается по мере продолжения случайного блуждания. Это показало, что SL содержится в RLP., класс задач, решаемых за полиномиальное время и логарифмическое пространство с помощью вероятностных машин, которые ошибочно отклоняют менее 1/3 времени. Заменив случайное блуждание универсальной последовательностью обхода, Aleliunas et al. также показал, что SL содержится в L / poly , классе неоднородной сложности задач, решаемых детерминированно в логарифмическом пространстве с помощью полиномиальных советов .

В 1989 г. Бородин и др. усилил этот результат, показав, что дополнение USTCON, определяющее, находятся ли две вершины в разных компонентах связности, также находится в RLP . [5] Это поместило USTCON и SL в co- RLP и на пересечение RLP и co- RLP , что является ZPLP , классом задач, которые имеют лог-пространство, ожидаемое полиномиальное время и рандомизированные алгоритмы без ошибок.

В 1992 году Нисан , Семереди и Вигдерсон наконец нашли новый детерминированный алгоритм для решения USTCON, используя только log 1,5 n пространства. [6] Это было немного улучшено, но до Рейнгольда не было более значительных достижений.

В 1995 году Нисан и Та-Шма показали удивительный результат , заключающийся в том, что SL закрывается при дополнении, что в то время многие считали ложным; то есть SL = co- SL . [7] Точно так же, если проблема может быть решена путем сведения ее к графу и запроса, находятся ли две вершины в одном компоненте, ее также можно решить, сведя ее к другому графу и спросив, находятся ли две вершины в разных компонентах. Однако статья Рейнгольда позже сделает этот результат излишним.

Одно из наиболее важных следствий SL = co- SL состоит в том, что L SL = SL ; то есть детерминированная машина в лог-пространстве с оракулом для SL может решать проблемы в SL (тривиально), но не может решать никаких других проблем. Это означает, что не имеет значения, используем ли мы сводимость Тьюринга или сводимость многих единиц, чтобы показать, что проблема находится в SL ; они эквивалентны.

Прорыв октября 2004 статья Омер Рейнгольд показал , что USTCON фактически в L . [8] Поскольку USTCON является SL -полным, это означает, что SL = L , что существенно исключает полезность рассмотрения SL как отдельного класса. Несколько недель спустя аспирант Владимир Трифонов показал, что USTCON можно решить детерминированно, используя пространство O (log n log log n ) - более слабый результат - с использованием различных методов. [9]Не было предпринято значительных усилий по превращению алгоритма Рейнгольда для USTCON в практическую формулировку. В его статье (и в предшествующих ей) ясно указано, что они в первую очередь связаны с асимптотикой; в результате описываемый им алгоритм фактически требует памяти и времени. Это означает, что даже для алгоритма потребуется больше памяти, чем содержится на всех компьютерах в мире (килограммэкзэксабайт).

Последствия L = SL [ править ]

Крах L и SL имеет ряд серьезных последствий. Наиболее очевидно, что все SL -полные задачи теперь находятся в L и могут быть с пользой использованы при разработке алгоритмов детерминированного лог-пространства и полилогарифмического пространства. В частности, у нас есть новый набор инструментов для сокращения пространства журнала . Также теперь известно, что проблема в L тогда и только тогда, когда пространство журнала сводится к USTCON.

Сноски [ править ]

  1. ^ Льюис, Гарри Р .; Пападимитриу, Христос Х. (1980), «Симметричные пространственно-ограниченные вычисления», Труды Седьмого Международного коллоквиума по автоматам, языкам и программированию , конспект лекций по информатике, 85 , Берлин: Springer, стр. 374–384, doi : 10.1007 / 3-540-10003-2_85 , Руководство по ремонту  0589018. Журнальная версия опубликована как Lewis, Harry R .; Papadimitriou, Christos H. (1982), "Симметричные пространства-ограниченное вычисление", Теоретическая информатика , 19 (2): 161-187, DOI : 10,1016 / 0304-3975 (82) 90058-5 , MR 0666539 
  2. ^ Альварес, Карме; Гринлоу, Raymond (2000), "компендиум проблем полных для симметричного логарифмического пространства", вычислительная сложность , 9 (2): 123-145, DOI : 10.1007 / PL00001603 , МР 1809688 .
  3. ^ Савич, Уолтер Дж. (1970), «Отношения между недетерминированными и детерминированными сложностями ленты», Журнал компьютерных и системных наук , 4 : 177–192, DOI : 10.1016 / S0022-0000 (70) 80006-X , hdl : 10338 .dmlcz / 120475 , MR 0266702 .
  4. ^ Aleliunas Ромас; Карп, Ричард М .; Липтон, Ричард Дж .; Ловас, Ласло ; Ракофф, Чарльз (1979), «Случайные блуждания, универсальные последовательности обходов и сложность задач лабиринта», Материалы 20-го ежегодного симпозиума по основам компьютерных наук , Нью-Йорк: IEEE, стр. 218–223, doi : 10.1109 / SFCS .1979.34 , Руководство по ремонту 0598110 .
  5. ^ Бородин, Аллан ; Кук, Стивен А .; Даймонд, Патрик У .; Ruzzo, Walter L .; Томпа, Мартин (1989), "Два применения индуктивного подсчета для задач комплементационных", SIAM журнал по вычислениям , 18 (3): 559-578, CiteSeerX 10.1.1.394.1662 , DOI : 10,1137 / 0218038 , МР 0996836  .
  6. ^ Нисан, Ноам ; Семереди, Эндре ; Вигдерсон, Ави (1992), «Ненаправленное соединение в пространстве O (log1.5n)», Труды 33-го ежегодного симпозиума по основам компьютерных наук , стр. 24–29, DOI : 10.1109 / SFCS.1992.267822.
  7. ^ Нисан, Ноам ; Та-Шма, Амнон (1995), "Симметричный logspace закрыт под комплемента", Чикаго Журнал теоретической информатики , статьи 1, MR 1345937 , ECCC TR94-003  .
  8. ^ Рейнгольд, Омер (2008), "неориентированный подключения в лог-пространстве", Журнал ACM , 55 (4): 1-24, DOI : 10,1145 / 1391289,1391291 , MR 2445014 .
  9. ^ Трифонов, Владимир (2008), " Алгоритм пространства O (log n log log n ) для ненаправленной st- связности", SIAM Journal on Computing , 38 (2): 449–483, doi : 10,1137 / 050642381 , MR 2411031 .

Ссылки [ править ]

  • C. Papadimitriou . Вычислительная сложность . Аддисон-Уэсли, 1994. ISBN 0-201-53082-1 . 
  • Майкл Сипсер . Введение в теорию вычислений . PWS Publishing Co., Бостон 1997 ISBN 0-534-94728-X .