Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеу күрделілігі теориясында, NL толық – бұл NL үшін толық тілдерді қамтитын күрделілік класы, яғни логарифмдік мөлшерде жад кеңістігін пайдаланатын детерминистік емес Тьюринг машинасымен шешілетін шешім проблемаларының класы. NL толық тілдері – NL класындағы ең "қиын" немесе "көрсеткішті" проблемалар болып табылады. Егер логарифмдік жад кеңістігінде кез келген бір NL толық проблеманы шешуге арналған детерминистік алгоритм болса, онда NL = L.
In computational complexity theory, NL complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. The NL complete languages are the most "difficult" or "expressive" problems in NL. If a deterministic algorithm exists for solving any one of the NL complete problems in logarithmic memory space, then NL = L.
Анықтамалар
NL – кіріс таспасы тек оқуға арналған және кіріс ұзындығының логарифміне пропорционал өлшеммен шектелген жеке оқу-жазу таспасы бар нон-детерминистік Тьюринг машинасымен шешілетін шешім проблемаларынан тұрады. Сол сияқты, L – дәл сол таспа ұзындығы шарттарымен детерминистік Тьюринг машинасымен шешілетін тілдер жиыны. Бұл машиналардың конфигурацияларының саны полиномдық болғандықтан, L және NL екеуі де детерминистік полиномдық уақытта шешілетін проблемалардың P классының ішкі жиындары болып табылады. Формальды түрде, егер шешім проблемасы NL класына жатса және NL класындағы кез келген басқа шешім проблемасын оған келтіруге болады, онда ол NL-толық деп аталады. Бұл анықтамада келтірулер, егер басқаша көрсетілмесе, детерминистік логарифмдік кеңістікте жұмыс істейтін көпке-бір келтірулер деп есептеледі.
NL consists of the decision problems that can be solved by a nondeterministic Turing machine with a read only input tape and a separate read write tape whose size is limited to be proportional to the logarithm of the input length. Similarly, L consists of the languages that can be solved by a deterministic Turing machine with the same assumptions about tape length. Because there are only a polynomial number of distinct configurations of these machines, both L and NL are subsets of the class P of deterministic polynomial time decision problems. Formally, a decision problem is NL complete when it belongs to NL, and has the additional property that every other decision problem in NL can be reduced to it. Unless otherwise specified, the reductions in this definition are assumed to be many one reductions by a deterministic logarithmic space algorithm.
Қасиеттері
Егер NL толық тілі X, L тіліне жатса, онда NL-дегі барлық басқа Y тілі де солай болады. Себебі, (NL толықтығы бойынша) Y мәселесінің y мысалын X мәселесінің x мысалына бейімдейтін детерминистік логарифмдік кеңістіктегі азайту r бар деп есептейік, сондай-ақ (X, L-де деп есептесек) X мәселесін шешуге арналған детерминистік логарифмдік кеңістіктегі алгоритм A бар деп есептейік. Осы есептеулерге сәйкес, Y тіліндегі y мәселесін логарифмдік кеңістікте r(y) кірісіндегі A алгоритмінің әрекетін модельдейтін алгоритм арқылы шешуге болады, r(y) үшін тек оқуға арналған таспаға қатынаудың әрбір сәттерін модельдеу үшін азайту алгоритмін пайдалана отырып. Иммерман-Зелепсени теоремасынан келіп шығатындай, егер тіл ко-NL толық болса (яғни, оның толықтығы NL толық болса), онда тілдің өзі де NL толық болады.
If an NL complete language X could belong to L, then so would every other language Y in NL. For, suppose (by NL completeness) that there existed a deterministic logspace reduction r that maps an instance y of problem Y to an instance x of problem X, and also (by the assumption that X is in L) that there exists a deterministic logspace algorithm A for solving problem X. With these assumptions, a problem y in language Y could be solved in logarithmic space by an algorithm that simulates the behavior of algorithm A on input r(y), using the reduction algorithm to simulate each access to the read only tape for r(y). It follows from the Immerman–Szelepcsényi theorem that, if a language is co NL complete (that is, if its complement is NL complete) then the language is also NL complete itself.
Мысалдар
NL-дің маңызды толық проблемасы ST байланысы (немесе "жету мүмкіндігі") (Papadimitriou 1994 Thrm. 16.2), яғни берілген бағытталған граф G және сол графтың s және t екі түйіні үшін s-тен t-ге дейін жол бар екенін анықтау мәселесі. ST байланысы NL класында екендігін көрсетуге болады, себебі біз s түйінінен бастап, басқа қолжетімді түйіндерге беймәлімдікпен (nondeterministically) жүреміз. Кез келген басқа NL алгоритмінің есептеу күйінің графигін қарастыра отырып, және егер бастапқы күйден қабылдау күйіне беймәлімдікпен (nondeterministik) жол болса ғана басқа алгоритм қабылдайтынын ескере отырып, ST байланысы NL қиын екенін көрсетуге болады. NL-дің тағы бір маңызды толық проблемасы – 2 қанағаттандырылатындық (Papadimitriou 1994 Thrm. 16.3), яғни конъюнктивті қалыпты түріндегі, әрбір клаузада екі айнымалысы бар Буль формуласының қанағаттандырылатындығын анықтау мәселесі. Берілген өзгермелі ұзындығы бар кодтың бірегей дешифровкалануы мәселесі co-NL толық екені көрсетілді; Риттер Sardinas–Patterson алгоритмінің түрімен бірнеше екіұшты декодталған тізбекті табу мәселесі NL класына жататынын көрсетті. Immerman–Szelepcsényi теоремасы бойынша, бірегей дешифровкалану NL толық екендігі де шығады. Ұсыныс логикасы, алгебра, сызықтық жүйелер, графтар, шекті автоматтары, контекстсіз грамматика бойынша қосымша NL толық проблемалар Жонс (1976) еңбегінде тізімделген.
One important NL complete problem is ST connectivity (or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST connectivity can be seen to be NL hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state. Another important NL complete problem is 2 satisfiability (Papadimitriou 1994 Thrm. 16.3), the problem of determining whether a boolean formula in conjunctive normal form with two variables per clause is satisfiable. The problem of unique decipherability of a given variable length code was shown to be co NL complete by ; Rytter used a variant of the Sardinas–Patterson algorithm to show that the complementary problem, finding a string that has multiple ambiguous decodings, belongs to NL. Because of the Immerman–Szelepcsényi theorem, it follows that unique decipherability is also NL complete. Additional NL complete problems on Propositional Logic, Algebra, Linear System, Graph, Finite Automata, Context free Grammar are listed in Jones (1976).