|
|
| Строка 2: |
Строка 2: |
| | | | |
| | ===Определение=== | | ===Определение=== |
| − | Язык <tex dpi="100">A</tex> является <tex dpi="100">\mathbf{NL}</tex>-полным (<tex dpi="100">\mathbf{NLC}</tex>), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">\mathbf{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
| |
| | | | |
| − | Язык <tex>A</tex> является <tex>\mathrm{NL}</tex>-полным (<tex>\mathrm{NLC}</tex>), если он принадлежит классу <tex>\mathrm{NL}</tex> и любой другой язык <tex>A'</tex> из <tex>\mathrm{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти. | + | Язык <tex>A</tex> является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык <tex>A'</tex> из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти. |
| − | | |
| − | Язык <tex dpi="100">A</tex> является <tex dpi="100">\mathrm{NL}</tex>-полным (<tex dpi="100">\mathrm{NLC}</tex>), если он принадлежит классу <tex dpi="100">\mathrm{NL}</tex> и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">\mathrm{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
| |
| − | | |
| − | Язык <tex dpi="100">A</tex> является NL-полным (NLC), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из NL можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
| |
| − | | |
| − | Язык <tex dpi="100">A</tex> является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык <tex dpi="100">A'</tex> из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
| |
| − | | |
| − | Язык <tex dpi="100">A</tex> является <tex dpi="100">NL</tex>-полным ('''NLC'''), если он принадлежит классу <tex dpi="100">NL</tex> и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">NL</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
| |
| − | | |
| − | Язык <tex>A</tex> является <tex>NL</tex>-полным ('''NLC'''), если он принадлежит классу <tex>NL</tex> и любой другой язык <tex>A'</tex> из <tex>NL</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.
| |
| − | | |
| − | Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык ''A<nowiki>'</nowiki>'' из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к ''A'', притом сведение будет использовать логарифмическое количество памяти.
| |
| | То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной. | | То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной. |
| | | | |
| Строка 25: |
Строка 12: |
| | ===Доказательство=== | | ===Доказательство=== |
| | | | |
| − | Рассмотрим язык ''B'' <tex>B</tex> из класса '''NL'''. | + | Рассмотрим язык <tex>B</tex> из класса '''NL'''. |
| − | Для каждого слова ''x'' <tex>x</tex> необходимо определять его принадлежность ''B'' используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти. | + | Для каждого слова <tex>x</tex> необходимо определять его принадлежность <tex dpi="100">B</tex> используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти. |
| − | | |
| − | Так как ''A'' '''NL'''-полон, то существует такая функция ''f'' <tex>f</tex> (использующая ''O''(log ''n'') дополнительной памяти), что <tex>x \in B \Leftrightarrow f(x) \in A</tex>.
| |
| | | | |
| − | Используя логарифмическое количество памяти ''B'' сводится к языку ''A'', который уже лежит в '''L'''.
| + | Так как <tex>A</tex> '''NL'''-полон, то существует такая функция <tex>f</tex> (использующая ''O''(log ''n'') дополнительной памяти), что <tex>x \in B \Leftrightarrow f(x) \in A</tex>. |
| | + | <tex>A</tex> принадлежит '''L''', поэтому мы можем определить принадлежность <tex>x</tex> языку <tex>B</tex> с необходимыми условиями. |
| | | | |
| − | Тонкость состоит в том, что мы не можем сохранить
| + | Однако, результат работы функции <tex>f</tex> сохранить невозможно, так как он может занимать более ''O''(log ''n'') памяти. |
| | + | Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата. |
| | | | |
| | ==Примеры NL-полных задач== | | ==Примеры NL-полных задач== |
| | | | |
| | [[NL-полнота задачи о достижимости в графе]] | | [[NL-полнота задачи о достижимости в графе]] |
В классе NL выделяют подкласс полных в этом классе задач.
Определение
Язык [math]A[/math] является NL-полным (NLC), если он принадлежит классу NL и любой другой язык [math]A'[/math] из NL можно свести по Карпу к [math]A[/math], притом сведение будет использовать логарифмическое количество памяти.
То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
Теорема
Если в классе L существует такой язык [math]A[/math], что он NL-полон, то NL = L.
Доказательство
Рассмотрим язык [math]B[/math] из класса NL.
Для каждого слова [math]x[/math] необходимо определять его принадлежность [math]B[/math] используя лишь детерминированные выборы и O(log n) дополнительной памяти.
Так как [math]A[/math] NL-полон, то существует такая функция [math]f[/math] (использующая O(log n) дополнительной памяти), что [math]x \in B \Leftrightarrow f(x) \in A[/math].
[math]A[/math] принадлежит L, поэтому мы можем определить принадлежность [math]x[/math] языку [math]B[/math] с необходимыми условиями.
Однако, результат работы функции [math]f[/math] сохранить невозможно, так как он может занимать более O(log n) памяти.
Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.
Примеры NL-полных задач
NL-полнота задачи о достижимости в графе
