SL (сложность) - SL (complexity)

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

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 цвета?
  • У двух неориентированных графов одинаковое количество связанные компоненты ?
  • Имеет ли граф четное число связных компонентов?
  • Для данного графа существует ли цикл, содержащий данное ребро?
  • Сделайте покрывающий леса двух графов имеют одинаковое количество ребер?
  • Для графа, все ребра которого имеют разные веса, является ли данное ребро в графе минимальный вес, охватывающий лес ?
  • Эксклюзивный или 2-выполнимость: дана формула, требующая, чтобы Икся xor Иксj справедливы для ряда пар переменных (Икся,Иксj), есть ли присвоение переменным, которое делает это верным?

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

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

Важные результаты

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

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

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

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

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

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

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

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

Последствия L = SL

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

Сноски

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

Рекомендации