СЛ (сложность)

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

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

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

Источник

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

${\mathsf {L}}\subseteq {\mathsf {SL}}\subseteq {\mathsf {NL}}$

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

Полные проблемы

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

• УСТКОН
• Моделирование симметричных машин Тьюринга: принимает ли СТМ заданные входные данные в определенном пространстве, заданные в унарном формате?
• Пути, не пересекающиеся по вершинам: существует ли k путей между двумя вершинами, разделяющих вершины только в конечных точках? (обобщение USTCON, эквивалентное вопросу, является ли граф k -связным)
• Является ли данный граф двудольным или, что то же самое, имеет ли он раскраску в два цвета?
• Имеют ли два неориентированных графа одинаковое количество компонент связности ?
• Имеет ли граф четное количество связных компонент?
• Существует ли в графе цикл, содержащий заданное ребро?
• Имеют ли остовные леса двух графов одинаковое количество ребер?
• Учитывая граф, все его ребра имеют разные веса, находится ли данное ребро в остовном лесу минимального веса ?
• Исключительная или 2- выполнимость : учитывая формулу, требующую, чтобы $x_{i}$ или $x_{j}$ справедливы для ряда пар переменных $(x_{i},x_{j})$, есть ли присвоение переменным, которое делает это истинным?

Дополнения всех этих задач имеются и в SL, поскольку, как мы увидим, SL замкнут относительно дополнений.

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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