Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік ғылымда, st байланысы немесе STCON – бағытталған графтың s және t төбелері үшін t төбесіне s төбесінен жете алу мүмкіндігін анықтайтын шешімдік есеп.
In computer science, st connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.
Формалды түрде, бұл шешімдік есеп былай беріледі:
Formally, the decision problem is given by
.
Күрделілігі
Жақын уақыттағы компьютерде st байланысы тереңдікке бірінші іздеу немесе ендікке бірінші іздеу арқылы сызықтық уақытта оңай шешіледі. Есептеу күрделілігіндегі осы мәселеге қызығушылық есептеудің шектеулі формаларына қатысты күрделілігімен байланысты. Мысалы, логистикалық емес Тьюринг машинасымен, тек логарифмдік көлемде жадты пайдалана отырып шешілетін мәселелер класы NL деп аталады. st байланыс мәселесі NL класында екенін көрсетуге болады, себебі детерминистік емес Тьюринг машинасы жолдың келесі түйінін болжап табуы мүмкін, ал сақталуы тиіс жалғыз ақпарат – жолдың жалпы ұзындығы және қазіргі уақытта қарастырылып жатқан түйін. Алгоритм мақсатты түйін t-ге жеткен жағдайда немесе жолдың ұзындығы n-ден (графиктегі түйіндер саны) асып кеткен жағдайда тоқтатылады. st байланысының толықтыруы, st байланысы жоқ деп белгілі, ол да NL класына жатады, себебі Иммерман-Сзелепчени теоремасы бойынша NL = coNL. Атап айтқанда, st байланыс мәселесі шын мәнінде NL-толық, яғни NL класындағы әрбір мәселе логарифмдік кеңістіктегі азайту арқылы байланысқа келтіріледі. Бұл бірінші реттік азайтулардың күшті жағдайы үшін де дұрыс. NL класындағы кез келген тілден STCON-ға логарифмдік кеңістіктегі азайту келесідей жүзеге асырылады: NL класындағы тілді қабылдайтын детерминистік емес логарифмдік кеңістікті Тьюринг машинасы M қарастырылсын. Жұмыс жадында логарифмдік кеңістік ғана болғандықтан, Тьюринг машинасының барлық мүмкін күйлері (күй – ішкі автоматтың күйі, бас орны және жұмыс жадының мазмұны) полиномдық санымен шешілген. Детерминистік логарифмдік кеңістікті машинаның барлық мүмкін күйлерін графтың түйіндеріне бейнелейік, және егер v күйіне u күйінен детерминистік емес машинаның бір қадамында жетуге болады, онда u мен v арасына қабырға қоямыз. Машина қабылдай ма деген мәселе бастапқы күйден қабылдау күйіне жолдың бар-жоқтығы мәселесімен бірдей. Савич теоремасы алгоритмді O(log2 n) детерминистік кеңістікте симуляциялауға кепілдік береді. Бағытталмаған графтар үшін осы мәселе бағытталмаған st байланысы деп аталады және Омер Рейнгольд оның L класында екенін көрсетті. Бұл зерттеу оған 2005 жылғы Грейс Мюррей Хоппер сыйлығын әкелді. Бұрын бағытталмаған st байланысы SL класы үшін толық екені белгілі болған, сондықтан Рейнгольдтың жұмысы SL класы L класымен бірдей екенін көрсетті. Алмасу графтарында мәселе P-толық.
On a sequential computer, st connectivity can easily be solved in linear time by either depth first search or breadth first search. The interest in this problem in computational complexity concerns its complexity with respect to more limited forms of computation. For instance, the complexity class of problems that can be solved by a non deterministic Turing machine using only a logarithmic amount of memory is called NL. The st connectivity problem can be shown to be in NL, as a non deterministic Turing machine can guess the next node of the path, while the only information which has to be stored is the total length of the path and which node is currently under consideration. The algorithm terminates if either the target node t is reached, or the length of the path so far exceeds n, the number of nodes in the graph. The complement of st connectivity, known as st non connectivity, is also in the class NL, since NL = coNL by the Immerman–Szelepcsényi theorem. In particular, the problem of st connectivity is actually NL complete, that is, every problem in the class NL is reducible to connectivity under a log space reduction. This remains true for the stronger case of first order reductions The log space reduction from any language in NL to STCON proceeds as follows: Consider the non deterministic log space Turing machine M that accepts a language in NL. Since there is only logarithmic space on the work tape, all possible states of the Turing machine (where a state is the state of the internal finite state machine, the position of the head and the contents of the work tape) are polynomially many. Map all possible states of the deterministic log space machine to vertices of a graph, and put an edge between u and v if the state v can be reached from u within one step of the non deterministic machine. Now the problem of whether the machine accepts is the same as the problem of whether there exists a path from the start state to the accepting state. Savitch's theorem guarantees that the algorithm can be simulated in O(log2 n) deterministic space. The same problem for undirected graphs is called undirected s t connectivity and was shown to be in L by Omer Reingold. This research won him the 2005 Grace Murray Hopper Award. Undirected st connectivity was previously known to be complete for the class SL, so Reingold's work showed that SL is the same class as L. On alternating graphs, the problem is P complete .