NL-полнота — различия между версиями
Ulyantsev (обсуждение | вклад) |
Assaron (обсуждение | вклад) (→Определение) |
||
| Строка 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 dpi="100">A</tex> является <tex dpi="100">\mathrm{NL}</tex>-полным (<tex dpi="100">\mathrm{NLC}</tex>), если он принадлежит классу NL и любой другой язык <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> является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык <tex dpi="100">A'</tex> из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти. | ||
Версия 18:55, 8 апреля 2010
В классе NL выделяют подкласс полных в этом классе задач.
Определение
Язык является -полным (), если он принадлежит классу NL и любой другой язык из можно свести по Карпу к , притом сведение будет использовать логарифмическое количество памяти.
Язык является -полным (), если он принадлежит классу NL и любой другой язык из можно свести по Карпу к , притом сведение будет использовать логарифмическое количество памяти.
Язык является NL-полным (NLC), если он принадлежит классу NL и любой другой язык из NL можно свести по Карпу к , притом сведение будет использовать логарифмическое количество памяти.
Язык является NL-полным (NLC), если он принадлежит классу NL и любой другой язык из NL можно свести по Карпу к , притом сведение будет использовать логарифмическое количество памяти.
Язык является -полным (NLC), если он принадлежит классу и любой другой язык из можно свести по Карпу к , притом сведение будет использовать логарифмическое количество памяти.
Язык является -полным (NLC), если он принадлежит классу и любой другой язык из можно свести по Карпу к , притом сведение будет использовать логарифмическое количество памяти.
Язык A является NL-полным (NLC), если он принадлежит классу NL и любой другой язык A' из NL можно свести по Карпу к A, притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
Теорема
Если в классе L существует такой язык , что он NL-полон, то NL = L.
Доказательство
Рассмотрим язык B из класса NL. Для каждого слова x необходимо определять его принадлежность B используя лишь детерминированные выборы и O(log n) дополнительной памяти.
Так как A NL-полон, то существует такая функция f (использующая O(log n) дополнительной памяти), что .
Используя логарифмическое количество памяти B сводится к языку A, который уже лежит в L.
Тонкость состоит в том, что мы не можем сохранить
