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

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

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

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

• 1 Источник
• 2 Полные проблемы
• 3 Важные результаты
• 4 Последствия L = SL
• 5 Сноски
• 6 Источники

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

$L\; \subseteq \; SL\; \subseteq \; NL\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{L\}\; \backslash \; substeq\; \backslash \; mathrm\; \{SL\}\; \backslash \; substeq\; \backslash \; mathrm\; \{NL\}\}$

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

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

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

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

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

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

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

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

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

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

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

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

Прорывная статья в октябре 2004 г., опубликованная Омером Рейнгольдом, показала, что USTCON на самом деле находится в L. Поскольку USTCON является SL -завершенным, это означает, что SL= L, по существу, устраняет полезность рассмотрения SL как отдельного класса. Несколько недель спустя аспирант Владимир Трифонов показал, что USTCON может быть решена детерминированно, используя пространство O (log n log log n) - более слабый результат - с использованием различных методов. Не было предпринято значительных усилий по превращению алгоритма Рейнгольда для USTCON в практическую формулировку. В его статье (и в предшествующих ей) ясно указано, что они в первую очередь связаны с асимптотикой; в результате описанный им алгоритм фактически займет $64\; 32\; log\; log\; N\; \{\backslash \; displaystyle\; 64\; ^\; \{32\}\; \backslash ,\; \backslash \; log\; N\}$памяти и $O\; (N\; 64\; 32)\; \{\backslash \; displaystyle\; O\; (N\; ^\; \{64\; ^\; \{32\}\})\}$время. Это означает, что даже для $N\; =\; 2\; \{\backslash \; displaystyle\; N\; =\; 2\}$алгоритму потребуется больше памяти, чем содержится на всех компьютерах в мире (килограммексагексабайт).

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

1. ^Льюис, Гарри Р. ; Пападимитриу, Христос Х. (1980), «Симметричные пространственно-ограниченные вычисления», Труды Седьмого Международного коллоквиума по автоматам, языкам и программированию, Конспекты лекций по информатике, 85, Берлин: Springer, стр. 374–384, doi :10.1007/3-540-10003-2_85, MR 0589018. Версия журнала опубликована как Льюис, Гарри Р. ; Пападимитриу, Христос Х. (1982), «Симметричные пространственно-ограниченные вычисления», Теоретическая информатика, 19(2): 161–187, doi : 10.1016 / 0304-3975 (82) 90058-5, MR 0666539
2. ^Альварес, Карме; Гринлоу, Раймонд (2000), «Полный сборник задач для симметричного логарифмического пространства», Computational Complexity, 9 (2): 123–145, doi : 10.1007 / PL00001603, MR 1809688.
3. ^Сэвич, Уолтер Дж. (1970), «Взаимосвязь между недетерминированными и детерминированными сложностями ленты», Journal of Computer and System Sciences, 4 : 177–192, doi : 10.1016 / S0022-0000 (70) 80006-X, hdl : 10338.dmlcz / 120475, MR 0266702.
4. ^Алелиунас, Ромас; Карп, Ричард М. ; Липтон, Ричард Дж. ; Ловас, Ласло ; Ракофф, Чарльз (1979), «Случайные блуждания, универсальные последовательности обходов и сложность задач лабиринта», Труды 20-го ежегодного симпозиума по основам компьютерных наук, Нью-Йорк: IEEE, pp. 218–223, doi : 10.1109 / SFCS.1979.34, MR 0598110.
5. ^Бородин, Аллан ; Кук, Стивен А. ; Даймонд, Патрик В.; Ruzzo, Walter L.; Томпа, Мартин (1989), «Два применения индуктивного счета для задач дополнения», SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX 10.1. 1.394.1662, doi : 10.1137 / 0218038, MR 0996836.
6. ^Нисан, Ноам ; Семереди, Эндре ; Вигдерсон, Ави (1992), «Ненаправленное соединение в пространстве O (log1.5n)», Труды 33-го ежегодного симпозиума по основам компьютерных наук, стр. 24–29, doi : 10.1109 / SFCS.1992.267822.
7. ^Нисан, Ноам ; Та-Шма, Амнон (1995), «Симметричное логическое пространство закрыто при дополнении», Чикагский журнал теоретической информатики, статья 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 по вычислениям, 38(2): 449–483, doi : 10.1137 / 050642381, MR 2411031.

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