Сложность SL: Равенство L и связь с задачей связности графа.

Введение

В теории вычислительной сложности SL (Symmetric Logspace или Sym L) – это класс сложности задач, логарифмически сводимых к USTCON (ненаправленная связность s-t), которая представляет собой задачу определения, существует ли путь между двумя вершинами в ненаправленном графе, или, иными словами, находятся ли две вершины в одном связном компоненте. Эта задача также называется задачей о достижимости в ненаправленном графе. Не имеет значения, используется ли многократная сводимость или сводимость по Тьюрингу. Хотя изначально SL описывался в терминах симметричных машин Тьюринга, эта эквивалентная формулировка очень сложна, и на практике используется определение сводимости. USTCON является частным случаем STCON (достижимость в ориентированном графе), задачи определения существования ориентированного пути между двумя вершинами в ориентированном графе, которая является полной для NL. Поскольку USTCON является SL-полной, большинство достижений, влияющих на USTCON, также влияют на SL. Таким образом, они тесно связаны и рассматриваются совместно. В октябре 2004 года Омер Рейнгольд доказал, что SL = L.

Происхождение

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

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

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

Существуют известные классические алгоритмы, такие как поиск в глубину и поиск в ширину, которые решают USTCON за линейное время и используют линейное пространство. Их существование, показанное задолго до определения SL, доказывает, что SL содержится в P. Также несложно показать, что USTCON, а следовательно и SL, находится в NL, поскольку мы можем просто недетерминированно выбирать на каждой вершине следующую вершину для посещения, чтобы найти путь, если он существует. Однако первым нетривиальным результатом для SL стала теорема Савича, доказанная в 1970 году, которая предоставила алгоритм, решающий USTCON в пространстве log2 n. В отличие от поиска в глубину, этот алгоритм непрактичен для большинства приложений из-за потенциально суперполиномиального времени работы. Следствием этого является то, что USTCON, и, следовательно, SL, находится в (На самом деле, теорема Савича дает более сильный результат, что NL содержится в ). Хотя в течение 22 лет не было (однородных) детерминированных улучшений алгоритма Савича, в 1979 году Алелиунас и др. нашли высокопрактичный вероятностный алгоритм, работающий в логарифмическом пространстве: просто начните с одной вершины и выполняйте случайное блуждание, пока не найдете другую (и примите) или пока не истечет заданный предел времени (и отклоните). Ложные отклонения совершаются с небольшой ограниченной вероятностью, которая экспоненциально уменьшается с увеличением продолжительности случайного блуждания. Это показало, что SL содержится в RLP, классе задач, разрешимых за полиномиальное время и использующих логарифмическое пространство с вероятностными машинами, которые отклоняют неправильно менее чем в 1/3 случаев. Заменив случайное блуждание универсальной последовательностью обхода, Алелиунас и др. также показали, что SL содержится в L/poly, неоднородном классе сложности задач, разрешимых детерминированно в логарифмическом пространстве с полиномиальными подсказками. В 1989 году Бородин и др. усилили этот результат, показав, что дополнение к USTCON, определяющее, находятся ли две вершины в разных связных компонентах, также находится в RLP. Это поместило USTCON и SL в co RLP и в пересечение RLP и co RLP, которое является ZPLP, классом задач, требующих логарифмического пространства, ожидаемого полиномиального времени и рандомизированных алгоритмов без ошибок. В 1992 году Нисан, Сземереди и Вигдерсон наконец нашли новый детерминированный алгоритм для решения USTCON, использующий только пространство log1.5 n. Это было немного улучшено, но значительных успехов до Рейнгольда достигнуто не было. В 1995 году Нисан и Та Шма показали удивительный результат, что SL замкнут относительно дополнения, что в то время многие считали ложным; то есть SL = co SL. Эквивалентно, если задачу можно решить, сведя ее к графу и спрашивая, находятся ли две вершины в одной компоненте, ее также можно решить, сведя ее к другому графу и спрашивая, находятся ли две вершины в разных компонентах. Однако статья Рейнгольда позже сделала этот результат избыточным. Одним из наиболее важных следствий SL = co SL является то, что LSL = SL; то есть детерминированная машина с логарифмическим пространством и оракулом для SL может решать задачи в SL (тривиально), но не может решать никакие другие задачи. Это означает, что не имеет значения, используем ли мы редуцируемость Тьюринга или редуцируемость много-к-одному, чтобы показать, что задача находится в SL; они эквивалентны. Прорывная статья Омера Рейнгольда, опубликованная в октябре 2004 года, показала, что USTCON на самом деле находится в L. Поскольку USTCON является SL-полной задачей, это подразумевает, что SL = L, по сути, сводя на нет полезность рассмотрения SL как отдельного класса. Через несколько недель аспирант Владимир Трифонов показал, что USTCON можно решить детерминированно, используя пространство — более слабый результат — с использованием других методов. Не было предпринято существенных усилий по преобразованию алгоритма Рейнгольда для USTCON в практическую реализацию. В его статье (и в предшествующих ей) явно указано, что они в первую очередь обеспокоены асимптотикой; в результате описанный им алгоритм фактически потребует памяти и времени. Это означает, что даже для , алгоритму потребуется больше памяти, чем содержится во всех компьютерах мира (килоэкзаэкзаэкзабайт).

There are well known classical algorithms such as depth first search and breadth first search which solve USTCON in linear time and space. Their existence, shown long before SL was defined, proves that SL is contained in P. It's also not difficult to show that USTCON, and so SL, is in NL, since we can just nondeterministically guess at each vertex which vertex to visit next in order to discover a path if one exists. The first nontrivial result for SL, however, was Savitch's theorem, proved in 1970, which provided an algorithm that solves USTCON in log2 n space. Unlike depth first search, however, this algorithm is impractical for most applications because of its potentially superpolynomial running time. One consequence of this is that USTCON, and so SL, is in (Actually, Savitch's theorem gives the stronger result that NL is in .) Although there were no (uniform) deterministic space improvements on Savitch's algorithm for 22 years, a highly practical probabilistic log space algorithm was found in 1979 by Aleliunas et al. : simply start at one vertex and perform a random walk until you find the other one (then accept) or until time has passed (then reject). False rejections are made with a small bounded probability that shrinks exponentially the longer the random walk is continued. This showed that SL is contained in RLP, the class of problems solvable in polynomial time and logarithmic space with probabilistic machines that reject incorrectly less than 1/3 of the time. By replacing the random walk by a universal traversal sequence, Aleliunas et al. also showed that SL is contained in L/poly, a non uniform complexity class of the problems solvable deterministically in logarithmic space with polynomial advice. In 1989, Borodin et al. strengthened this result by showing that the complement of USTCON, determining whether two vertices are in different connected components, is also in RLP. This placed USTCON, and SL, in co RLP and in the intersection of RLP and co RLP, which is ZPLP, the class of problems which have log space, expected polynomial time, no error randomized algorithms. In 1992, Nisan, Szemerédi, and Wigderson finally found a new deterministic algorithm to solve USTCON using only log1.5 n space. This was improved slightly, but there would be no more significant gains until Reingold. In 1995, Nisan and Ta Shma showed the surprising result that SL is closed under complement, which at the time was believed by many to be false; that is, SL = co SL. Equivalently, if a problem can be solved by reducing it to a graph and asking if two vertices are in the same component, it can also be solved by reducing it to another graph and asking if two vertices are in different components. However, Reingold's paper would later make this result redundant. One of the most important corollaries of SL = co SL is that LSL = SL; that is, a deterministic, log space machine with an oracle for SL can solve problems in SL (trivially) but cannot solve any other problems. This means it does not matter whether we use Turing reducibility or many one reducibility to show a problem is in SL; they are equivalent. A breakthrough October 2004 paper by Omer Reingold showed that USTCON is in fact in L. Since USTCON is SL complete, this implies that SL = L, essentially eliminating the usefulness of consideration of SL as a separate class. A few weeks later, graduate student Vladimir Trifonov showed that USTCON could be solved deterministically using space—a weaker result—using different techniques. There has not been substantial effort into turning Reingold's algorithm for USTCON into a practical formulation. It is explicit in his paper (and those leading up to it) that they are primarily concerned with asymptotics; as a result, the algorithm he describes would actually take memory, and time. This means that even for , the algorithm would require more memory than contained on all computers in the world (a kiloexaexaexabyte).

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

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