Кіріспе
Есептеу күрделілігі теориясында NL (Nondeterministic Logarithmic space) – бұл шешімдік есептерді қамтитын күрделілік класы, оларды логарифмдік мөлшерде жадты пайдаланатын нон-детерминистік Тьюринг машинасы шеше алады. NL – детерминистік Тьюринг машинасының лог-кеңістік есептері класы L-дің жалпыламасы. Кез келген детерминистік Тьюринг машинасы сонымен қатар нон-детерминистік Тьюринг машинасы болғандықтан, L класы NL класының ішінде орналасқан. NL формальды түрде есептеу ресурсының нон-детерминистік кеңістігі (немесе NSPACE) арқылы NL = NSPACE(log n) ретінде анықталады. Күрделілік теориясының маңызды нәтижелері осы күрделілік класын басқа кластармен байланыстыруға мүмкіндік береді, осы арқылы қолданылатын ресурстардың салыстырмалы қуаты туралы білуге болады. Алгоритмдер саласындағы нәтижелер осы ресурспен қандай есептерді шешуге болатынын көрсетеді. Күрделілік теориясының көп бөлігі сияқты, NL туралы көптеген маңызды сұрақтар әлі де ашық (Компьютер ғылымындағы шешілмеген есептерді қараңыз). Кейде NL, төмендегі ықтималдық анықтамасына сәйкес RL деп те аталады; алайда, бұл атау көбінесе NL-ге тең емес, кездейсоқ логарифмдік кеңістікке сілтеме жасау үшін қолданылады.
NL-толық проблемалар
Бірнеше мәселелер, соның ішінде ST байланысы және 2 қанағаттандырылатындық, логарифмдік кеңістікте азайту бойынша NL-толық екені белгілі. ST байланысы бағытталған графтың S және T түйіндері үшін T түйініне S түйінінен жете аламыз ба деген сұрақ қояды. 2 қанағаттандырылатындық мәселесінде әрбір клауза екі литералдың дизъюнкциясы болатын логикалық формула берілгенде, осы формуланы дұрыс ететін айнымалыларға тағайындама бар ма деп сұралады. Мысалы, ¬ белгісі жоқты білдірсе:
Контейнерлер
Белгілі болғандай, екі қанағаттандыруға арналған полиномиалдық уақыт алгоритмі болғандықтан, кіріктірілген, бірақ кіріктірілгені немесе кіріктірілгені белгісіз. Белгілі болғандай, , мұнда – толықтырылғандары кіріктірілген тілдер класы. Бұл нәтиже (Имерман–Сзелепсейньи теоремасы) 1987 жылы Нил Иммерман мен Роберт Сзелепсейньи тәуелсіз түрде ашқан; олар бұл жұмысы үшін 1995 жылы Гедель сыйлығын алды. Сұлба күрделілігінде кіріктірілген иерархияға орналасуы мүмкін. Пападимитриу 1994, 16.1 теоремасы бойынша:
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Дәлірек айтқанда, кіріктірілген. Белгілі болғандай, логарифмдік кеңістікте және шексіз уақытта кездейсоқ алгоритмдермен шешілетін проблемалар класымен, қатесіз тең. Алайда, кіріктірілгені немесе кіріктірілгені тең екені белгілі немесе сенімді емес, оны кейбір авторлар кіріктірілген және деп атайды.
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Савич теоремасын пайдаланып, детерминистік кеңістікпен байланыстыруға болады, ол кез келген нондетерминистік алгоритмді детерминистік машинада ең көп дегенде квадраттық көбірек кеңістікте модельдеуге болатынын айтады. Савич теоремасынан тікелей мынаны білеміз:
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Бұл 1994 жылы белгілі ең күшті детерминистік кеңістік кіріктірілімі болды (Пападимитриу 1994, 16.4.10 проблемасы, «Симметриялық кеңістік»). Үлкен кеңістік кластары квадраттық өсуге әсер етпегендіктен, нондетерминистік және детерминистік кластар тең екені белгілі, мысалы, бізде .
More precisely, is contained in It is known that is equal to , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to or , the polynomial time restrictions of and , which some authors refer to as and
We can relate to deterministic space using Savitch's theorem, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
This was the strongest deterministic space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have .
Ықтималдық анықтамасы
Болжайық, C – логарифмдік кеңістікте ықтималдық Тьюринг машиналарымен шешілетін шешім проблемаларының күрделілік класы, олар ешқашан дұрыс қабылдамайды, бірақ уақыттың 1/3-інен кем уақытта дұрыс қабылдамайды; мұны бір жақты қате деп атайды. 1/3 тұрақтысы кездейсоқ; 0 ≤ x < 1/2 шартын қанағаттандыратын кез келген x жеткілікті. Шындығында, C = NL. C, оның детерминистік әріптесі L-ден айырмашылығы, полиномдық уақытпен шектелмейді, себебі конфигурацияларының саны полиномдық болғанымен, шексіз циклден шығу үшін кездейсоқтықты пайдалана алады. Егер оны полиномдық уақытпен шектелсек, онда RL класын аламыз, ол NL класына кіреді, бірақ NL-мен тең екені белгілі емес және солай деп есептелмейді. C = NL екенін көрсететін қарапайым алгоритм бар. C NL класына кіреді, өйткені:
Егер жол тілде болмаса, барлық есептеу жолдары бойынша қабылдаудан бас тартады. Егер жол тілде болса, NL алгоритмі кем дегенде бір есептеу жолы бойынша қабылдайды, ал C алгоритмі кем дегенде екі үшін екі бөлігі бойынша есептеу жолын қабылдайды. NL класы C класына кіреді екенін көрсету үшін, NL алгоритмін алып, ұзындығы n кездейсоқ есептеу жолын таңдаймыз және оны 2n рет орындаймыз. Ешқандай есептеу жолы n ұзындығынан аспайды және барлығы 2n есептеу жолы бар екенін ескерсек, қабылдайтын жолды табуға жақсы мүмкіндік бар (төменнен тұрақтымен шектелген). Бір ғана мәселе – 2n-ге дейін санайтын бинарлық санағышты логарифмдік кеңістікте сақтауға орын жетпейді. Оны болдырмау үшін, оны кездейсоқ санағышпен ауыстырамыз, ол жай ғана n монетаны лақтырып, барлығы түйреуіне (бас жағына) тоқтап, қабылдаудан бас тартады. Бұл оқиғаның ықтималдығы 2−n болғандықтан, тоқтағанға дейін орташа есеппен 2n қадам жасауымыз керек. Ол тек қатар тізілген түйреулердің (бас жағы) жалпы санын сақтау керек, оны логарифмдік кеңістікте санауға болады. Immerman–Szelepcsényi теоремасына сәйкес, NL толықтырулар бойынша жабық, сондықтан осы ықтималдық есептеулердегі бір жақты қате нөлдік жақты қатемен алмастырылуы мүмкін. Яғни, бұл мәселелерді логарифмдік кеңістікті пайдаланатын және ешқашан қателік жасамайтын ықтималдық Тьюринг машиналарымен шешуге болады. Машинадан тек полиномдық уақытты пайдалануды талап ететін сәйкес күрделілік класы ZPLP деп аталады. Осылайша, кеңістікке ғана назар салсақ, кездейсоқтық пен нон-детерминизм бірдей қуатты болып көрінеді.
If the string is not in the language, both reject along all computation paths. If the string is in the language, an NL algorithm accepts along at least one computation path and a C algorithm accepts along at least two thirds of its computation paths. To show that NL is contained in C, we simply take an NL algorithm and choose a random computation path of length n, and execute this 2n times. Because no computation path exceeds length n, and because there are 2n computation paths in all, we have a good chance of hitting the accepting one (bounded below by a constant). The only problem is that we don't have room in log space for a binary counter that goes up to 2n. To get around this we replace it with a randomized counter, which simply flips n coins and stops and rejects if they all land on heads. Since this event has probability 2−n, we expect to take 2n steps on average before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space. Because of the Immerman–Szelepcsényi theorem, according to which NL is closed under complements, the one sided error in these probabilistic computations can be replaced by zero sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires the machine to use only polynomial time is called ZPLP. Thus, when we only look at space, it seems that randomization and nondeterminism are equally powerful.
Куәліктің анықтамасы
NL NP сияқты сыныптарға ұқсас сертификаттармен эквивалентті түрде сипатталуы мүмкін. Тек бір рет оқылатын қосымша кіріс таспасы бар, детерминистік логарифмдік кеңістікпен шектелген Тьюринг машинасы қарастырылсын. Тіл, егер және тек осындай Тьюринг машинасы қосымша кіріс таспасындағы тиісті сертификатты таңдау арқылы тілдегі кез келген сөзді қабылдаса және сертификаттан тәуелсіз тілдегі емес сөзді қабылдамаса, ғана NL тіліне жатады. Cem Say және Abuzer Yakaryılmaz жоғарыда айтылған детерминистік логарифмдік кеңістікті Тьюринг машинасының, тек тұрақты мөлшерде кездейсоқ биттерді пайдалануға рұқсат етілген, шектелген қателікпен жұмыс істейтін тұрақты кеңістікті Тьюринг машинасымен алмастырылатынын дәлездеді.
Сипаттамалық күрделілік
NL-ді қарапайым логикалық сипаттау бар: ол бірінші реттік логикада транзитивті жабу операторы қосылған тілдерді дәл қамтиды.
Жабылу қасиеттері
NL класы толықтыру, біріктіру және, демек, қиылысу, тізбектеу және Клейне жұлдызы операциялары бойынша жабық.