Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеу күрделілігі теориясында SL (симметриялық логикалық кеңістік немесе Sym L) – USTCON (бағытталмаған s t байланысы) проблемасына логикалық кеңістікте кемітілетін проблемалардың күрделілік класы. Бұл бағытталмаған графтың екі төбесі арасында жолдың бар-жоғын анықтау мәселесі, немесе екі төбе бір-бірімен байланысқан компонентке жата ма, жоқ па, анықтау мәселесі болып сипатталады. Бұл проблема бағытсыз қолжетімділік проблемасы деп те аталады. Көптеген бірлік кеміту немесе Тьюринг кеміту қолданылғаны маңызды емес. Алғашқыда симметриялық Тьюринг машиналары тұрғысынан сипатталғанмен, бұл эквиваленттік формула өте күрделі, ал практикада кеміту анықтамасы қолданылады. USTCON – STCON (бағытталған қолжетімділік) проблемасының ерекше жағдайы, яғни бағытталған графтың екі төбесі арасында бағытталған жолдың бар-жоғын анықтау мәселесі, және ол NL үшін толық. USTCON SL толық болғандықтан, USTCON-ға әсер ететін көптеген жетістіктер SL-ге де әсер етеді. Осылайша, олар байланысты және бірге талқыланады. 2004 жылдың қазанында Омер Рейнгольд SL = L екенін көрсетті.
In computational complexity theory, SL (Symmetric Logspace or Sym L) is the complexity class of problems log space reducible to USTCON (undirected s t connectivity), which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice. USTCON is a special case of STCON (directed reachability), the problem of determining whether a directed path between two vertices in a directed graph exists, which is complete for NL. Because USTCON is SL complete, most advances that impact USTCON have also impacted SL. Thus they are connected, and discussed together. In October 2004 Omer Reingold showed that SL = L.
Шығу тегі
SL алғаш рет 1982 жылы Гарри Р. Льюис және Христос Пападимитриу есімді ғалымдар анықтады. Олар USTCON мәселесін орналастыруға болатын жаңа сынып іздестіріп жатқан, себебі бұл мәселені бұрынғыда ең жақсы жағдайда NL сыныбына ғана жатқызуға болады, бірақ ол детерминизмді қажет етпейтіндей сезілді. Олар симметриялық Тьюринг машинасының түсінігін енгізіп, оны SL сыныбын анықтау үшін пайдаланды, USTCON мәселесі SL үшін толық екенін көрсетті және мынаны дәлелдеді:
SL was first defined in 1982 by Harry R. Lewis and Christos Papadimitriou, who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in NL, despite seeming not to require nondeterminism. They defined the symmetric Turing machine, used it to define SL, showed that USTCON was complete for SL, and proved that
L – логарифмдік кеңістікте қарапайым детерминистік Тьюринг машинасымен шешілетін мәселелердің белгілі бір класы, ал NL – логарифмдік кеңістікте детерминистік емес Тьюринг машинасымен шешілетін мәселелердің класы. Кейінірек талқыланатын Рейнгольдтың зерттеуі, логарифмдік кеңістікпен шектелген жағдайда симметриялық Тьюринг машинасының қуаты қарапайым детерминистік Тьюринг машинасымен тең екенін көрсетті.
where L is the more well known class of problems solvable by an ordinary deterministic Turing machine in logarithmic space, and NL is the class of problems solvable by nondeterministic Turing machines in logarithmic space. The result of Reingold, discussed later, shows that in fact, when limited to log space, the symmetric Turing machine is equivalent in power to the deterministic Turing machine.
Маңызды нәтижелер
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-ді RLP және 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-ға логарифмдік кеңістікте азайтылатын болса, дегені белгілі болды.
The collapse of L and SL has a number of significant consequences. Most obviously, all SL complete problems are now in L, and can be gainfully employed in the design of deterministic log space and polylogarithmic space algorithms. In particular, we have a new set of tools to use in log space reductions. It is also now known that a problem is in L if and only if it is log space reducible to USTCON.