http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=109.188.223.77&*Викиконспекты - Вклад участника [ru]2026-06-11T18:40:58ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_L,_NL,_coNL._NL-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D0%B8%D0%B6%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=23112Классы L, NL, coNL. NL-полнота задачи о достижимости2012-05-31T22:06:06Z<p>109.188.223.77: /* NL-полнота */</p>
<hr />
<div>{{Определение<br />
|definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<br />
<tex>L = \mathrm{DSPACE}(O(\log n))</tex><br />
}}<br />
<br />
{{Определение<br />
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<br />
<tex>\mathrm{NL} = \mathrm{NSPACE}(O(\log n))</tex><br />
}}<br />
<br />
{{Определение<br />
|definition='''Класс <tex>\mathrm{coNL}</tex>''' — множество языков, дополнение до которых принадлежит <tex>\mathrm{NL}</tex>.<br />
}}<br />
<br />
{{ Теорема<br />
| statement = <tex>\mathrm{L} \subset \mathrm{NL} \subset \mathrm{P}.</tex><br />
| proof = <br />
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \in \mathrm{NL}</tex>.<br />
2. Число конфигураций машины, использующей <tex>O(\log n)</tex> памяти не превышает <tex>2^{O(\log n)} = n^{O(1)} = poly(n)</tex>, а, следовательно, машина завершает свою работу за <tex>O(poly(n))</tex> времени. Следовательно, <tex>\mathrm{NL} \in \mathrm{P}.</tex><br />
}}<br />
<br />
==NL-полнота==<br />
{{Определение<br />
|definition='''Язык <tex>X</tex>'''называют <tex>\mathrm{NL}</tex>-полным, если <tex>X \in \mathrm{NL}</tex> и <tex>\forall Y : Y \in NL, Y \leq_L X</tex>.<br />
}}<br />
<br />
{{ Теорема<br />
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.<br />
| proof = <br />
Задача <tex>CONN = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.<br />
<br />
Докажем, что <tex>CONN \in \mathrm{NL}</tex>.<br />
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.<br />
<br />
Алгоритм<br />
<br />
1. Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)<br />
<br />
2. Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.<br />
<br />
3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.<br />
<br />
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.<br />
<br />
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>CONN</tex> с использованием не более чем логарифмической памяти.<br />
<br />
Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>CONN</tex> для которой будет эквивалентно решению данной задачи.<br />
<br />
Любая машина Тьюринга, которая принимает некоторый язык <tex>\mathrm{L}</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.<br />
<br />
Очевидно, что для любого слова из языка <tex>\mathrm{L}</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>\mathrm{L}</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.<br />
<br />
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы из него и проверка возможности перехода.<br />
<br />
}}<br />
<br />
==Теорема Иммермана==<br />
{{ Теорема<br />
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex><br />
| proof = <br />
Решим задачу <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка <tex>\mathrm{CONN}</tex>.<br />
Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</tex>, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.<br />
<br />
Определим <tex>R_i</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.<br />
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.<br />
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.<br />
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.<br />
{{Лемма<br />
| statement = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.<br />
| proof = <br />
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.<br />
'''Enum'''(<tex>s, i, ri, G</tex>)<br />
<tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов<br />
'''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа<br />
'''continue''' or find path //недетерминированно угадываем путь из s до v или переходим к следующей вершине<br />
<tex>counter</tex>++<br />
'''return'''' <tex>v</tex> //выдаем вершину, до которой угадали путь<br />
'''if''' (<tex>counter \geq r_i</tex>) //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу<br />
'''accept'''<br />
'''reject''' //не нашли <tex>r_i</tex> вершин, не допускаем<br />
<br />
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.<br />
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.<br />
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. <br />
'''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск.<br />
<br />
Теперь, имея '''Enum''', можно по индукции находить <tex>r_i</tex>. <br />
Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. <br />
Пусть известно значение <tex>r_i</tex>. <br />
Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.<br />
<br />
<br />
'''Next'''(<tex>s, i, r_i, G</tex>)<br />
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r \in R_{i+1}</tex><br />
'''for''' <tex>v = 1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex><br />
'''for''' <tex>u : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex><br />
'''if''' (<tex>u</tex> '''in''' '''Enum'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex><br />
<tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата<br />
'''break''' <br />
'''return''' <tex>r</tex><br />
<br />
<br />
Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.<br />
Для каждого из них перебираются все ребра, в него входящие.<br />
Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>.<br />
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enum'''.<br />
<br />
Теперь напишем алгоритм, который будет недетерминированно решать задачу <tex>\mathrm{NCONN}</tex> на логарифмической памяти.<br />
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.<br />
Вычисление <tex>r_{n-1}</tex> происходит путем вызова '''Next''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.<br />
<br />
<br />
'''NCONN'''(<tex>G, s, t</tex>)<br />
<tex>r_n = 1</tex> //<tex>r_0 = 1</tex><br />
'''for''' <tex>i = 0..n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex><br />
<tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>)<br />
'''if''' (<tex>t1</tex> '''in''' '''Enum'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept'''<br />
'''reject'''<br />
'''else'''<br />
'''accept'''<br />
<br />
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, и для вызываемых '''Next''' и '''Enum''' необходимо <tex>O(\log |G|)</tex> памяти.<br />
<br />
Таким образом показано, что <tex>\mathrm{NCONN} \in \mathrm{NL}</tex>.<br />
Поскольку <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>, то аналогичным образом <tex>\mathrm{NCONN} \in \mathrm{coNLC}</tex>.<br />
Получаем, что любую задачу из <tex>\mathrm{coNL}</tex> можно свести к задаче из <tex>\mathrm{NL}</tex>, а значит <tex>\mathrm{coNL} \subset \mathrm{NL}</tex>.<br />
Из соображений симметрии <tex>\mathrm{NL} \subset \mathrm{coNL}</tex>, а значит <tex>\mathrm{coNL} = \mathrm{NL}</tex>.<br />
<br />
}}<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_L,_NL,_coNL._NL-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D0%B8%D0%B6%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=23111Классы L, NL, coNL. NL-полнота задачи о достижимости2012-05-31T22:03:34Z<p>109.188.223.77: </p>
<hr />
<div>{{Определение<br />
|definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<br />
<tex>L = \mathrm{DSPACE}(O(\log n))</tex><br />
}}<br />
<br />
{{Определение<br />
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<br />
<tex>\mathrm{NL} = \mathrm{NSPACE}(O(\log n))</tex><br />
}}<br />
<br />
{{Определение<br />
|definition='''Класс <tex>\mathrm{coNL}</tex>''' — множество языков, дополнение до которых принадлежит <tex>\mathrm{NL}</tex>.<br />
}}<br />
<br />
{{ Теорема<br />
| statement = <tex>\mathrm{L} \subset \mathrm{NL} \subset \mathrm{P}.</tex><br />
| proof = <br />
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \in \mathrm{NL}</tex>.<br />
2. Число конфигураций машины, использующей <tex>O(\log n)</tex> памяти не превышает <tex>2^{O(\log n)} = n^{O(1)} = poly(n)</tex>, а, следовательно, машина завершает свою работу за <tex>O(poly(n))</tex> времени. Следовательно, <tex>\mathrm{NL} \in \mathrm{P}.</tex><br />
}}<br />
<br />
==NL-полнота==<br />
{{Определение<br />
|definition='''Язык <tex>X</tex>'''называют <tex>\mathrm{NL}</tex>-полным, если <tex>X \in \mathrm{NL}</tex> и <tex>\forall Y : Y \in NL, Y \leq_L X</tex>.<br />
}}<br />
<br />
{{ Теорема<br />
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.<br />
| proof = <br />
Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.<br />
<br />
Докажем, что <tex>\mathrm{CONN} \in \mathrm{NL}</tex>.<br />
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.<br />
<br />
Алгоритм<br />
<br />
1. Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)<br />
<br />
2. Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.<br />
<br />
3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.<br />
<br />
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.<br />
<br />
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>\mathrm{CONN}</tex> с использованием не более чем логарифмической памяти.<br />
<br />
Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>\mathrm{CONN}</tex> для которой будет эквивалентно решению данной задачи.<br />
<br />
Любая машина Тьюринга, которая принимает некоторый язык <tex>\mathrm{L}</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.<br />
<br />
Очевидно, что для любого слова из языка <tex>\mathrm{L}</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>\mathrm{L}</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.<br />
<br />
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы из него и проверка возможности перехода.<br />
<br />
}}<br />
<br />
<br />
<br />
==Теорема Иммермана==<br />
{{ Теорема<br />
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex><br />
| proof = <br />
Решим задачу <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка <tex>\mathrm{CONN}</tex>.<br />
Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</tex>, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.<br />
<br />
Определим <tex>R_i</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.<br />
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.<br />
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.<br />
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.<br />
{{Лемма<br />
| statement = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.<br />
| proof = <br />
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.<br />
'''Enum'''(<tex>s, i, ri, G</tex>)<br />
<tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов<br />
'''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа<br />
'''continue''' or find path //недетерминированно угадываем путь из s до v или переходим к следующей вершине<br />
<tex>counter</tex>++<br />
'''return'''' <tex>v</tex> //выдаем вершину, до которой угадали путь<br />
'''if''' (<tex>counter \geq r_i</tex>) //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу<br />
'''accept'''<br />
'''reject''' //не нашли <tex>r_i</tex> вершин, не допускаем<br />
<br />
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.<br />
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.<br />
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. <br />
'''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск.<br />
<br />
Теперь, имея '''Enum''', можно по индукции находить <tex>r_i</tex>. <br />
Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. <br />
Пусть известно значение <tex>r_i</tex>. <br />
Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.<br />
<br />
<br />
'''Next'''(<tex>s, i, r_i, G</tex>)<br />
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r \in R_{i+1}</tex><br />
'''for''' <tex>v = 1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex><br />
'''for''' <tex>u : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex><br />
'''if''' (<tex>u</tex> '''in''' '''Enum'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex><br />
<tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата<br />
'''break''' <br />
'''return''' <tex>r</tex><br />
<br />
<br />
Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.<br />
Для каждого из них перебираются все ребра, в него входящие.<br />
Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>.<br />
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enum'''.<br />
<br />
Теперь напишем алгоритм, который будет недетерминированно решать задачу <tex>\mathrm{NCONN}</tex> на логарифмической памяти.<br />
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.<br />
Вычисление <tex>r_{n-1}</tex> происходит путем вызова '''Next''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.<br />
<br />
<br />
'''NCONN'''(<tex>G, s, t</tex>)<br />
<tex>r_n = 1</tex> //<tex>r_0 = 1</tex><br />
'''for''' <tex>i = 0..n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex><br />
<tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>)<br />
'''if''' (<tex>t1</tex> '''in''' '''Enum'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept'''<br />
'''reject'''<br />
'''else'''<br />
'''accept'''<br />
<br />
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, и для вызываемых '''Next''' и '''Enum''' необходимо <tex>O(\log |G|)</tex> памяти.<br />
<br />
Таким образом показано, что <tex>\mathrm{NCONN} \in \mathrm{NL}</tex>.<br />
Поскольку <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>, то аналогичным образом <tex>\mathrm{NCONN} \in \mathrm{coNLC}</tex>.<br />
Получаем, что любую задачу из <tex>\mathrm{coNL}</tex> можно свести к задаче из <tex>\mathrm{NL}</tex>, а значит <tex>\mathrm{coNL} \subset \mathrm{NL}</tex>.<br />
Из соображений симметрии <tex>\mathrm{NL} \subset \mathrm{coNL}</tex>, а значит <tex>\mathrm{coNL} = \mathrm{NL}</tex>.<br />
<br />
}}<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A1%D1%8D%D0%B2%D0%B8%D1%87%D0%B0._%D0%A1%D0%BE%D0%B2%D0%BF%D0%B0%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_NPS_%D0%B8_PS&diff=23028Теорема Сэвича. Совпадение классов NPS и PS2012-05-31T13:44:05Z<p>109.188.223.77: /* Определение */</p>
<hr />
<div>=Класс PS=<br />
<br />
== Определение ==<br />
{{Определение <br />
|definition=<tex>\mathrm{PS(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br><br />
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{DSPACE}(p(n)) </tex><br />
}}<br />
<br />
{{Определение <br />
|definition=<tex>\mathrm{NPS(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br><br />
<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{NSPACE}(p(n))</tex><br />
}}<br />
<br />
== Связь класса PS с другими классами теории сложности ==<br />
{{Теорема<br />
|statement =<br />
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.<br />
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement =<br />
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.<br />
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.<br />
}}<br />
<br />
=Теорема Сэвича=<br />
<br />
{{Теорема<br />
|statement =<br />
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br><br />
<br />
То есть, если недетерминированная машина Тьюринга может решить проблему используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.<br />
|proof = <br />
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти).<br />
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.<br />
<br />
Пусть <tex>L \in \mathrm{NSPACE}(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br><br />
Рассмотрим вспомогательную функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</tex> за не более, чем <tex>2^k</tex> переходов:<br />
<br />
'''Reach''' (I, J, k)<br />
'''if''' (k = 0)<br />
'''return''' (I <tex>\vdash</tex> J) or (I = J);<br />
'''else'''<br />
'''for''' (Y) // перебор промежуточных конфигураций<br />
'''if''' Reach(I, Y, k-1) and Reach(Y, J, k-1)<br />
'''return''' true;<br />
'''return''' false;<br />
<br />
Эта функция имеет глубину рекурсии <tex>O(k)</tex>, на каждом уровне рекурсии использует <tex>O(f(n))</tex> памяти для хранения текущих конфигураций.<br />
<br />
Рассмотрим машину Тьюринга <tex>m</tex>, распознающую язык <tex>L</tex>. Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>m</tex> имеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Головка на входной ленте может быть в одной из n позиций и в одной из <tex>f(n)</tex> на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}</tex>.<br />
<br />
Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность к языку <tex>L</tex>:<br />
<br />
'''Check''' (x, L)<br />
'''for''' (T) // перебор конфигураций, которые содержат допускающие состояния<br />
'''if''' Reach(S, T, <tex>\log \left(2^{df(n)}\right)</tex>)<br />
'''return''' true;<br />
'''return''' false;<br />
<br />
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции <tex>Reach</tex>. И если слово не допускается за <tex>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. <br />
В итоге функция <tex>Reach</tex> имеет глубину рекурсии <tex>\log{2}^{df(n)}=O(f(n))</tex>, на каждом уровне рекурсии используется <tex>O(f(n))</tex> памяти. Тогда всего эта функция использует <tex>O(f(n)^2)</tex> памяти.<br />
}}<br />
<br />
==Следствие==<br />
<tex>\mathrm{PS}=\mathrm{NPS}</tex><br />
<br />
=Вывод=<br />
<tex>\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PS} = \mathrm{NPS}</tex>.<br />
<br />
Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.<br />
<br />
<br />
=Источники=<br />
* Michael Sipser. Introduction to the theory of computation.<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D1%8B_%D0%BE_%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B8_%D1%91%D0%BC%D0%BA%D0%BE%D1%81%D1%82%D0%BD%D0%BE%D0%B9_%D0%B8%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F%D1%85&diff=23023Теоремы о временной и ёмкостной иерархиях2012-05-31T12:36:57Z<p>109.188.223.77: </p>
<hr />
<div>{{Определение<br />
|id=space_foo<br />
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по памяти''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex>, используя не более <tex>f(x)</tex> памяти.<br />
}}<br />
<br />
{{Теорема<br />
|about=о емкостной иерархии<br />
|id=space<br />
|statement=Пусть даны две конструируемые по памяти функции <tex>f</tex> и <tex>g</tex> такие, что <tex>\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0</tex>, тогда <tex>DSPACE(f(n)) \varsubsetneq DSPACE(g(n))</tex>.<br />
|proof=<br />
Понятно, что <tex>DSPACE(f(n)) \subseteq DSPACE(g(n))</tex>, поскольку программа, ограниченная по памяти функцией <tex>f</tex>, проходит ограничение <tex>g</tex>.<br /><br />
Используя диагональный метод, докажем, что включение строгое. Рассмотрим функцию <tex>h(n)=\sqrt{f(n)g(n)}</tex> и язык <tex>L=\{x|x(x)\Bigr|_{S\leq h(|x|)}\neq 1\}</tex>, где запись <tex>S\leq h(|x|)</tex> означает, что программа запускается с лимитом памяти <tex>h(|x|)</tex>. Иначе говоря, <tex>L</tex> — это язык программ, которые не допускают собственный код, используя не более <tex>h(|x|)</tex> памяти. Докажем, что <tex>L\in DSPACE(g(n))\setminus DSPACE(f(n))</tex>.<br/><br />
Так как <tex>h(n)=o(g(n))</tex>, то очевидно, что <tex>L \in DSPACE(g(n))</tex>. Действительно, для проверки принадлежности программы <tex>x</tex> языку достаточно запустить её с лимитом памяти <tex>h(|x|)</tex> и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более <tex>g(|x|)</tex> памяти в силу конструируемости функций <tex>f</tex> и <tex>g</tex> и накладываемых ограничений на память.<br /><br />
Предположим теперь, что <tex>L \in DSPACE(f(n))</tex>. Тогда существует программа <tex>p</tex>, распознающая язык <tex>L</tex> и использующая не более <tex>c \cdot f(n)</tex> памяти. Так как <tex>f(n)=o(h(n))</tex>, то <tex>\exists n_0: \forall n>n_0 \Rightarrow c\cdot f(n)<h(n)</tex>. Будем считать, что <tex>|p|>n_0</tex> (иначе добавим в программу пустые строки, искусственно увеличив её длину), тогда при вызове <tex>p(p)</tex> потребуется не более <tex>h(|p|)</tex> памяти. Выясним, принадлежит ли <tex>p</tex> языку <tex>L</tex>. Допустим, что <tex>p\in L</tex>, тогда <tex>p(p)=1</tex>, значит, <tex>p\notin L</tex> по определению языка <tex>L</tex>. Пусть теперь <tex>p\notin L</tex>. Но тогда <tex>p(p) \ne 1</tex>, следовательно, <tex>p\in L</tex>.<br />
Таким образом, язык <tex>L</tex> не может быть из <tex>DSPACE(f(n))</tex>, следовательно, язык из <tex>DSPACE(g(n))\setminus DSPACE(f(n))</tex> найден.}}<br />
<br />
{{Определение<br />
|id=time_foo<br />
|definition=Функция <tex>f(x)</tex> называется '''конструируемой по времени''', если можно вычислить <tex>f(x)</tex> по <tex>x</tex> за время не более <tex>f(x)</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|about=о временной иерархии<br />
|id=time<br />
|statement=Пусть даны две конструируемые по времени функции <tex>f</tex> и <tex>g</tex> такие, <span title="Здесь Sim(n) — время симуляции n шагов одной машины Тьюринга на другой машине" style="border-bottom: 1px dotted; cursor: help;">что</span> <tex>\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0</tex>, тогда <tex>DTIME(f(n)) \varsubsetneq DTIME(g(n))</tex>. <br />
|proof=Доказательство аналогично доказательству [[Теоремы о временной и емкостной иерархиях#space|теоремы о емкостной иерархии]].<br />
}}<br />
<br />
[[Категория:Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23022Класс P2012-05-31T12:27:18Z<p>109.188.223.77: /* Задача равенства P и NP */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.<br />
|proof =<br />
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>\mathrm{P}</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23020Класс P2012-05-31T11:32:12Z<p>109.188.223.77: /* Задача равенства P и NP */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.<br />
|proof =<br />
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>\mathrm{P}</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>\mathrm{P}</tex>, <tex>\mathrm{P}\subset \mathrm{NP}</tex>, так как для любой задачи класса <tex>\mathrm{P}</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>\mathrm{NP}</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23019Класс P2012-05-31T11:31:57Z<p>109.188.223.77: /* Задача равенства P и NP */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.<br />
|proof =<br />
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>\mathrm{P}</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>\mathrm{P}</tex>, <tex>\mathrm{P}\subset \mathrm{NP}</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>\mathrm{NP}</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23018Класс P2012-05-31T11:31:15Z<p>109.188.223.77: /* Примеры задач и языков из P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.<br />
|proof =<br />
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>\mathrm{P}</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23017Класс P2012-05-31T11:30:52Z<p>109.188.223.77: /* Соотношение классов Reg и P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.<br />
|proof =<br />
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23016Класс P2012-05-31T11:30:11Z<p>109.188.223.77: /* Соотношение классов CFL и P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>Reg \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.<br />
|proof =<br />
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23015Класс P2012-05-31T11:29:10Z<p>109.188.223.77: /* Соотношение классов Reg и P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>Reg \subset \mathrm{P}</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset \mathrm{P}</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23014Класс P2012-05-31T11:28:29Z<p>109.188.223.77: /* Свойства класса P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset P</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23013Класс P2012-05-31T11:26:44Z<p>109.188.223.77: /* Определение */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset P</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23012Класс P2012-05-31T11:23:00Z<p>109.188.223.77: /* Примеры задач и языков из P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>P = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset P</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=23011Класс P2012-05-31T11:14:55Z<p>109.188.223.77: /* Соотношение классов Reg и P */</p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>P = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset P</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_XOR_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%83_AC%E2%81%B0&diff=23006Теорема о непринадлежности XOR классу AC⁰2012-05-31T10:35:38Z<p>109.188.223.77: </p>
<hr />
<div>===Hastad’s switching lemma===<br />
{{Лемма<br />
|statement=<br />
Пусть <tex>f</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex><br />
|proof=<br />
}}<br />
Заметим, что для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.<br />
<br />
===Теорема===<br />
{{Определение<br />
|definition=<br />
<tex>\oplus~-</tex> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|язык]] над [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|алфавитом]] <tex>\left\{0, 1\right\}</tex>, состоящий из [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|слов]], содержащих нечетное число <tex>1.</tex><br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
<tex>\oplus \notin \mathrm{AC^0}</tex>.<br />
|proof=<br />
Рассмотрим произвольную схему из <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:<br />
# Выходная степень каждого элемента равна <tex>1</tex>.<br />
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.<br />
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.<br />
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.<br />
<br />
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью на <tex>1</tex> уменьшить глубину схемы, сохранив при этом число входов. Пусть <tex>n~-</tex> длина входной цепочки, а <tex>d~-</tex> глубина схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n^b</tex> было не меньше, чем число элементов в схеме. На каждом шаге случайным образом будем назначать все большее число переменных. Обозначим <tex>n_i~-</tex> число неназначенных переменных на <tex>i</tex>-ом шаге. Тогда на <tex>i + 1</tex>-ом шаге число назначенных переменных будет <tex>n_i - \sqrt{n_i}</tex>. Возьмем <tex>k_i=10b2^i.</tex><br />
<br />
[[Файл:beforeHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]<br />
<br />
Покажем, что после <tex>i+1</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне будет <tex>k_i</tex>. В самом деле, пусть нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Отсюда по лемме получаем, что с вероятностью <tex>1-\left(\frac{k_i^{10}}{n^{1/2^{i+1}}}\right) ^ {k_{i+1}/2}</tex> функцию можно записать в виде <tex>k_{i+1}</tex>-КНФ. При достаточно больших <tex>n</tex> это можно сделать с вероятность хотя бы <tex>1-\frac{1}{10n^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.<br />
<br />
[[Файл:afterHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i+1</tex>-ом шаге.]]<br />
<br />
Заметим, что лемма применяется не более, чем к <tex>n^b</tex> элементам исходной схемы. Тогда с вероятностью не менее <tex>9/10</tex> после <tex>d-2</tex>-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать <tex>k_{d-2}</tex> переменных. Однако функцию, распознающую <tex>\oplus,</tex> невозможно сделать постоянной, зафиксировав менее <tex>n</tex> переменных. Получили противоречие. Поскольку рассматривали произвольную схему из класса <tex>\mathrm{AC^0}</tex>, верно что <tex>\oplus \notin \mathrm{AC^0}.</tex><br />
}}<br />
<br />
===Источники===<br />
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_NC_%D0%B8_AC&diff=23005Классы NC и AC2012-05-31T10:35:25Z<p>109.188.223.77: </p>
<hr />
<div>==Определения==<br />
{{Определение<br />
|definition=<br />
<tex>\mathrm{NC^i}</tex> — множество языков, распознаваемых семейством логических схем полиномиального от <tex>n</tex> размера, глубиной <tex>O(log^i (n))</tex> и со степенью входа каждого элемента не более 2, причем существует детерминированная машина Тьюринга, принимающая на вход <tex>1^n</tex> и строящая соответствующую схему используя <tex>O(log(n))</tex> ячеек памяти, где <tex>n</tex> — длина входа.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, за исключением того, что степень входа элемента неограничена.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
<tex>\mathrm{NC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
<tex>\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}</tex>.<br />
}}<br />
<br />
==Теоремы==<br />
{{Теорема<br />
|statement=<tex>\mathrm{NC^i} \subset \mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex>.<br />
|proof=<br />
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> <br/><br />
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/><br />
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> <br/><br />
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Степень входа каждого элемента схемы <tex>C_n</tex> не превосходит полинома от <tex>n</tex>, поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более 2 следующим образом: <br/><br />
[[Файл:circuit.jpg]]<br />
<br />
При такой замене глубина схемы увеличится не более чем в <tex>log_2 r(n) = O(log(n))</tex> раз, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов она станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>.<br/><br />
При замене одного элемента будет добавлено не более <tex>r(n)</tex> элементов, потому, поскольку изначальный размер схемы был полиномиальным и каждый элемент мы заменили полиномиальным числом элементов, после всех замен размер схемы останется полиномиальным. <br />
}}<br />
'''Следствие:''' <tex>\mathrm{NC} = \mathrm{AC}</tex>.<br />
<br />
<br />
{{Теорема<br />
|statement=<tex>\mathrm{NC} \subseteq \mathrm{P}</tex>.<br />
|proof =<br />
Пусть <tex>L \in \mathrm{NC}</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex>, таких, что существует детерминированная машина Тьюринга, строящая схему по <tex>1^n</tex>, используя <tex>O(log(n))</tex> ячеек памяти. Конфигурация МТ задается положением головки и состоянием ячеек памяти, то есть у МТ может быть <tex>n \cdot 2^{O(log(n))} = O(n^2)</tex> конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно схема будет построена за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим её. На вычисление схемы будет затрачено полиномиальное время, так как размер схемы полиномиален.}}<br />
Равенство <tex>\mathrm{NC}</tex> и <tex>\mathrm{P}</tex> — неразрешенная на данный момент задача.<br />
<br />
<br />
{{Утверждение<br />
|about=тезис о связи <tex>\mathbf{NC}</tex> с параллельными алгоритмами<br />
|statement=<br />
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n))</tex> тогда и только тогда, когда <tex>L \in \mathrm{NC}</tex>.<br />
|proof=<br />
''(набросок доказательства)''<br />
<br />
Пусть <tex>L \in \mathrm{NC}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex>, где <tex>C_n</tex> размера <tex>N=O(poly(n))</tex> и имеет глубину <tex>O(log^d n)</tex>. Возьмем параллельный компьютер с <tex>N</tex> процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполняться параллельно. Тогда получаем, что всего потребуется <tex>O(log^d(n))</tex> времени. <br />
<br />
Пусть <tex>L</tex> распознается параллельным компьютером с <tex>N=O(poly(n))</tex> процессоров за время <tex>D=O(log^d n)</tex>. Построим схему глубины <tex>D</tex>, на каждом уровне которой будет по <tex>N</tex> элементов, таких, что <tex>i</tex>-й элемент на уровне <tex>t</tex> выполняет вычисления, производимые <tex>i</tex>-м процессором в момент времени <tex>t</tex>. Всего в схеме будет <tex>N \cdot D = O(poly(n)) \cdot O(log^d n) = O(poly(n))</tex> элементов.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0_%E2%80%94_%D0%9B%D0%B8%D0%BF%D1%82%D0%BE%D0%BD%D0%B0&diff=23004Теорема Карпа — Липтона2012-05-31T10:35:12Z<p>109.188.223.77: </p>
<hr />
<div>{{Лемма<br />
|statement= Пусть <tex>SAT \in P/poly </tex>, тогда существует семейство схем полиномиального размера <tex>D_n</tex>, таких, что для любой формулы <tex>\phi \in SAT</tex>, <tex>D_{|\phi|}(\phi)</tex> выводит набор значений, удовлетворяющий формуле.<br />
|proof=<br />
Если <tex>\phi</tex> не содержит переменных, то есть является тождественной единицей, решение задачи тривиально.<br />
Иначе, выберем любую переменную <tex>x</tex> из формулы <tex>\phi</tex>, и выполним подстановку <tex>x = 0</tex>. Получим формулу <tex>\phi_0</tex>. Если <tex>\phi_0 \in SAT</tex> (так как по условию теоремы <tex>SAT \in P/poly</tex>, такую проверку можно сделать за полиномиальное время, вычислив соответствующую схему), то мы свели задачу к аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой <tex>x = 1</tex>. Мы получили программу, работающую за полиномиальное время, а так как <tex>P \in P/poly</tex>, то и семейство требуемых схем.<br />
}}<br />
<br />
<br />
{{Теорема<br />
|author=Карп, Липтон<br />
|statement=<br />
Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.<br />
|proof=<br />
Так как <tex>NP \subset P/poly</tex>, то <tex>\mathrm{SAT} \in \mathrm{P/poly}</tex>, то есть для любого <tex>n</tex> найдётся схема полиномиального размера <tex> C_n</tex>, такая что <tex>C_{|\phi|}(\phi) = \left[\phi \in SAT\right]</tex>.<br />
Тогда, найдётся и схема полиномиального размера <tex> D_{|\phi|}</tex>, выдающая для <tex>\phi \in SAT</tex> набор значений, удовлетворяющий <tex>\phi</tex>.<br />
<br />
Рассмотрим язык <tex>L \in \Pi_2</tex>, <tex>L = \{z | \forall x </tex> <tex>\exists y </tex> <tex> \phi(x, y, z)\}</tex>.<br/><br />
Рассмотрим формулу <tex>\psi(x, z) = \exists y</tex> <tex>\phi(x, y, z)</tex> как экземпляр задачи <tex>SAT</tex>.<br/><br />
Тогда определение языка <tex>L</tex> можно переписать так: <tex>L=\{z | \forall x</tex> <tex> \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)\}</tex>.<br/><br />
Покажем что <tex>(\forall x</tex> <tex> \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)</tex> <tex>)\Leftrightarrow</tex> <tex>(\exists G : </tex> <tex> \forall x</tex> <tex>\phi(x, G(\psi(x, z)), z))</tex>.<br />
<br>Очевидно, из первого следует второе, так как <tex>\exists G = D_{|\psi(x, z)|}</tex>.<br />
Если первое ложно, то <tex>\exists x = x_0 : </tex> <tex>\forall y</tex> <tex>\phi(x, y, z) = 0</tex>, а значит <tex>\forall G </tex> <tex>\exists x = x_0 : \phi (x, G(\psi(x, z)), z)</tex>, то есть второе ложно.<br />
Итого, язык <tex>L=\{z | \exists G : </tex> <tex>\forall x</tex> <tex>\phi(x, G(\psi(x, z)), z)\}</tex>, значит <tex>L \in \Sigma_2</tex>.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%85%D0%B5%D0%BC%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B8_%D0%BA%D0%BB%D0%B0%D1%81%D1%81_P/poly&diff=23003Схемная сложность и класс P/poly2012-05-31T10:35:00Z<p>109.188.223.77: </p>
<hr />
<div>== Определения ==<br />
<br />
{{Определение<br />
|definition=<br />
<tex> PSIZE </tex> {{---}} класс языков, вычислимых семейством [[Реализация_булевой_функции_схемой_из_функциональных_элементов|логических схем]] <tex> \{C_n\}_{n>0} </tex> полиномиального размера с n входами и одним выходом, то есть: <tex>PSIZE=\{L | \forall n </tex> <tex> \exists C_n </tex>: <br />
#<tex> |C_n| \leqslant p(n)</tex>, где <tex> p </tex> {{---}} полином;<br />
#Input <tex> (C_n) = n </tex>;<br />
#Output <tex> (C_n) = 1 </tex>;<br />
#<tex>x \in L \iff C_{|x|}(x) = 1 \}</tex>. <br />
}} <br />
<br />
{{Определение<br />
|definition=<br />
Пусть C {{---}} сложностный класс, f {{---}} функция. Тогда <tex> C/f = \{L| </tex> существуют <tex> a_0, a_1, .. , a_n, .. </tex> {{---}} подсказки, программа p, удовлетворяющая ограничениям C:<br />
#<tex>|a_i| \leqslant f(i) </tex>;<br />
#<tex> x \in L \iff p(x, a_{|x|})=1 \}</tex>. <br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
<tex> P/poly = \bigcup\limits_{p \in poly} P/p </tex>. <br />
}}<br />
<br />
== Теоремы ==<br />
<br />
{{Теорема<br />
|statement=<br />
<tex> P \subset PSIZE </tex>.<br />
|proof=<br />
Пусть <tex> L \in P </tex>. Тогда существует машина Тьюринга m, распознающая язык L. Составим логическую схему для m, как мы сделали в [[Примеры_NP-полных_языков._Теорема_Кука|теореме Кука]], ее размеры ограничены полиномом, она допускает только слова из языка. Отсюда следует, что <tex> P \subset PSIZE </tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
<tex> PSIZE \subset P/poly</tex>.<br />
|proof=<br />
Пусть <tex> L \in PSIZE </tex>, x {{---}} входная строка. Тогда для L существуют логические схемы <tex> C_0, C_1, .., C_n, .. </tex>. В качестве подсказки для x предоставим логическую схему <tex> C_{|x|} </tex>. Программа p получает на вход x и <tex> C_{|x|} </tex> и возвращает значение, вычисляемое <tex> C_{|x|} </tex> для входа x. Запишем программу<br />
<tex> p(x, C_{|x|}) </tex>:<br />
'''return''' <tex>C_{|x|}(x) </tex><br />
<br />
Логическая схема <tex> C_{|x|} </tex> имеет полиномиальный размер. Оба условия для <tex> P/poly </tex> выполнены, <tex> PSIZE \subset P/poly</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
<tex> P/poly \subset PSIZE</tex>.<br />
|proof=<br />
Пусть <tex> L \in P/poly </tex>, x {{---}} входная строка. Тогда для L существуют подсказки <tex> a_0, a_1, .. , a_n, .. </tex>. Программа p по входу x и подсказке <tex> a_{|x|} </tex> определяет принадлежность x языку L. Зафиксируем длину входной строки x как n. Запишем p в виде логической схемы <tex> C_m </tex> ( <tex> m = n + |a_n| </tex>), которая принимает на вход слова длины n и подсказку <tex> a_n </tex>. Полученная схема будет полиномиального размера. Зашьем подсказку в самой схеме, то есть впишем в нее значения битов подсказки. Получим схему <tex> C_n </tex> полиномиального размера, принимающую слова длины n и определяющую их принадлежность языку L. Такие схемы можно получить для любой длины входа. Значит, <tex> P/poly \subset PSIZE </tex>. <br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D1%8B_%D0%BE_%D0%BA%D0%BE%D0%BB%D0%BB%D0%B0%D0%BF%D1%81%D0%B5_%D0%BF%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D0%B8%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D0%B8&diff=23002Теоремы о коллапсе полиномиальной иерархии2012-05-31T10:34:46Z<p>109.188.223.77: </p>
<hr />
<div>{{Лемма<br />
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.<br />
|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i</tex>.<br />
}}<br />
<br />
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==<br />
{{Теорема<br />
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.<br />
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>.<br/><br />
Докажем по индукции.<br/><br />
'''База'''. <tex>\Sigma_i = \Sigma_{i+1}</tex> из условия.<br/><br />
'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>.<br/><br />
Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. <tex>L = \{x \colon \exists y_1 \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex>\forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.<br />
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}</tex>.<br/><br />
Заметим, что <tex>L_f \in \Pi_{n+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>.<br/><br />
Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>.<br />
<tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex><br />
'''return''' <tex>R_{L_f}^n(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex><br />
То есть язык <tex>L \in \Sigma_{n+1}</tex>.<br />
}}<br />
<br />
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==<br />
{{Теорема<br />
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.<br />
|proof = <br />
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.<br />
<br />
Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \colon \exists y_1 \forall y_2 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1})\}</tex>. Обозначим <tex>\forall y_2 \exists y_3 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1}) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \colon f(x, y_1) = 1\}</tex>.<br><br />
Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>.<br/><br />
По определению сложностного класса <tex>\Sigma_i \; \exists R_{L_f}^i \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_{L_f}^i(\langle x, y_1 \rangle, y_2 \ldots y_{i+1})</tex>. Тогда <tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_L^i(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. <br/><br />
<tex>R_L^i(x, \langle y_1, y_2\rangle, y_3 \ldots, y_{i+1})</tex><br />
'''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3 \ldots y_{i+1})</tex><br />
Значит, <tex>L \in \Sigma_i</tex>.<br />
}}<br />
Заметим, что <tex>\Sigma_0 = \Pi_0 = \mathrm{P}</tex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.<br />
<br />
== См. также ==<br />
*[[Классы PH, Σ и Π]]<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_PH,_%CE%A3_%D0%B8_%CE%A0&diff=23001Классы PH, Σ и Π2012-05-31T10:34:13Z<p>109.188.223.77: </p>
<hr />
<div><br />
== Классы Σ и Π ==<br />
{{Определение<br />
|definition =<br />
<tex>\Sigma_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p</tex> {{---}} <tex>poly : \forall x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\},</tex><br/><br />
где <tex>L</tex> — формальный язык <tex>,Q = \exists</tex> для <tex>i = 2k$-$1,</tex> <tex>Q = \forall</tex> для <tex>i = 2k</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
<tex>\Pi_{i} = \{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p</tex> {{---}} <tex>poly : \forall x \in L \Leftrightarrow \forall y_{1} \exists y_{2} \forall y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},</tex><br/><br />
где <tex>L</tex> — формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k$-$1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.<br />
}}<br />
<br />
== Взаимоотношения между классами Σ и Π ==<br />
{{Теорема<br />
|statement = <tex>\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.<br />
|proof = Пусть <tex>L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)</tex>.<br/><br />
Проверим, что <tex>L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>.<br />
<br/><br />
<tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {<br />
return <tex>R(x,y_{1},\cdots,y_{i})</tex>;<br />
}<br />
Проверим, что <tex>L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>.<br />
<br/><br />
<tex>R''(x,y_{0},y_{1},\cdots,y_{i})</tex> {<br />
return <tex>R(x,y_{1},\cdots,y_{i})</tex>;<br />
}<br />
Т.о., <tex>\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement = <tex>\Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.<br />
|proof = Пусть <tex>L \in \Pi_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)</tex>.<br/><br />
Проверим, что <tex>L \in \Pi_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>.<br />
<br/><br />
<tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {<br />
return <tex>R(x,y_{1},\cdots,y_{i})</tex>;<br />
}<br />
Проверим, что <tex>L \in \Sigma_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \exists y_{0} \forall y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>.<br />
<br/><br />
<tex>R''(x,y_{0},y_{1},\cdots,y_{i})</tex> {<br />
return <tex>R(x,y_{1},\cdots,y_{i})</tex>;<br />
}<br />
Т.о., <tex>\Pi_{i} \subset \Sigma_{i+1}, \Pi_{i} \subset \Pi_{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement = <tex>\Sigma_{i} = co\Pi_{i}</tex>.<br />
|proof = <tex>co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p</tex> {{---}} <tex>poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}.</tex><br/><br />
Из самого выражения для <tex>co\Pi_{i}</tex> очевидно равенство.<br />
}}<br />
<br />
== Класс PH ==<br />
{{Определение<br />
|definition =<br />
<tex>PH_{1} = {\bigcup \atop {k \in \mathbb{N}}} \Sigma_{i}</tex>.<br/><br />
<tex>PH_{2} = {\bigcup \atop {k \in \mathbb{N}}} \Pi_{i}</tex>.<br/><br />
<tex>PH_{3} = {\bigcup \atop {k \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement = Все три определения класса <tex>PH</tex> эквивалентны, т.е. <tex>PH_{1} = PH_{2} = PH_{3}</tex>.<br />
|proof = <tex>\Sigma_{i} \subset \Pi_{i+1} \Rightarrow PH_{1} \subset PH_{2}</tex>.<br/><br />
<tex>\Pi_{i} \subset (\Sigma_{i+1} \cap \Pi_{i+1}) \subset (\Sigma_{i+1} \cup \Pi_{i+1}) \Rightarrow PH_{2} \subset PH_{3}</tex>.<br/><br />
<tex>\Pi_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Sigma_{i+1} \Rightarrow PH_{3} \subset PH_{1}</tex>.<br/><br />
Т.о., <tex>PH_{1} \subset PH_{2} \subset PH_{3} \subset PH_{1}</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement = <tex>PH \subset PS</tex>.<br />
|proof = Пусть <tex>L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)</tex>.<br/><br />
То есть, для перебора всех возможных значений <tex>y_{j}</tex> потребуется не более, чем <tex>i \cdot poly(|x|)</tex> памяти. Заметим, что <tex>i \cdot poly(|x|)</tex> тоже полином.<br />
Таким образом, для любого формального языка из <tex>PH</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>PH</tex> принадлежит <tex>PS</tex>.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D1%8B_L,_NL,_coNL._NL-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B4%D0%BE%D1%81%D1%82%D0%B8%D0%B6%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=23000Классы L, NL, coNL. NL-полнота задачи о достижимости2012-05-31T10:33:58Z<p>109.188.223.77: </p>
<hr />
<div>{{Определение<br />
|definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<br />
<tex>L = \mathrm{DSPACE}(O(\log n))</tex><br />
}}<br />
<br />
{{Определение<br />
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<br />
<tex>\mathrm{NL} = \mathrm{NSPACE}(O(\log n))</tex><br />
}}<br />
<br />
{{Определение<br />
|definition='''Класс <tex>\mathrm{coNL}</tex>''' — множество языков, дополнение до которых принадлежит <tex>NL</tex>.<br />
}}<br />
<br />
{{ Теорема<br />
| statement = <tex>L \in \mathrm{NL} \in P.</tex><br />
| proof = <br />
1. Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>L \in \mathrm{NL}</tex>.<br />
2. Число конфигураций машины, использующей <tex>O(\log n)</tex> памяти не превышает <tex>2^{O(\log n)} = n^{O(1)} = poly(n)</tex>, а, следовательно, машина завершает свою работу за <tex>O(poly(n))</tex> времени. Следовательно, <tex>\mathrm{NL} \in P.</tex><br />
}}<br />
<br />
==NL-полнота==<br />
{{Определение<br />
|definition='''Язык <tex>X</tex>'''называют <tex>\mathrm{NL}</tex>-полным, если <tex>X \in \mathrm{NL}</tex> и <tex>\forall Y : Y \in NL, Y \leq_L X</tex>.<br />
}}<br />
<br />
{{ Теорема<br />
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-полна.<br />
| proof = <br />
Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle</tex> : в графе G <tex>\exists </tex> путь из s в t<tex>\}</tex>.<br />
<br />
Докажем, что <tex>\mathrm{CONN} \in \mathrm{NL}</tex>.<br />
Для доказательства необходимо предъявить алгоритм для недетерминированной машины Тьюринга, который использует конечное число переменных, каждая из которых занимает <tex> O(\log n) </tex> памяти, где <tex> n </tex> - размер входа для задачи и за время порядка <tex> O(poly(n)) </tex> решает эту задачу.<br />
<br />
Алгоритм<br />
<br />
1. Начиная с вершины <tex> s </tex> недетерминированно переходим в одну из вершин, смежных с ней. (Очевидно, для этого необходимо конечное число переменных)<br />
<br />
2. Проверяем, правда ли, что текущая вершина совпадает с <tex> t </tex>. Если это так, возвращает TRUE.<br />
<br />
3. Отдельно считаем количество пройденных вершин. Как только это число превышает количество вершин в графе, возвращаем FALSE, так как посетили некоторую вершину дважды.<br />
<br />
Таким образом в каждый момент алгоритму достаточно хранить текущую вершину, количество посещенных вершин, финальную вершину <tex> t </tex> и некоторое число вспомогательных переменных, для совершения переходов. Все эти переменные принимают значения не более, чем максимальный номер вершины, то есть как раз занимают <tex> O(\log n) </tex> памяти.<br />
<br />
Теперь докажем, что любая задача из класса <tex>\mathrm{NL}</tex> сводится к задаче <tex>\mathrm{CONN}</tex> с использованием не более чем логарифмической памяти.<br />
<br />
Необходимо по данной задаче из <tex>\mathrm{NL}</tex> построить тройку <tex> \langle G, s, t \rangle </tex>, решение задачи <tex>\mathrm{CONN}</tex> для которой будет эквивалентно решению данной задачи.<br />
<br />
Любая машина Тьюринга, которая принимает некоторый язык <tex>\mathrm{L}</tex> из <tex>\mathrm{NL}</tex>, использует не более чем логарифмическое количество ячеек на рабочей ленте, и таким образом возможных мгновенных описаний этой машины Тьюринга <tex> O(poly(n)) </tex>. Каждому возможному мгновенному описанию машины Тьюринга будет соответствовать некоторая вершина в <tex> G </tex>, а каждому переходу из этого описания в другое (которых в недетерминированной машине Тьюринга конечное число) {{---}} ребро в графе <tex> G </tex>. За вершину <tex> s </tex> принимается вершина, соответствующая начальному состоянию машины, а из каждой вершины, соответствующей некоторому допускающему состоянию, добавляется переход в выделенную вершину <tex> t </tex>.<br />
<br />
Очевидно, что для любого слова из языка <tex>\mathrm{L}</tex>, то есть принимаемого данной машиной Тьюринга, будет существовать путь из <tex> s </tex> в <tex> t </tex> в построенном графе <tex> G </tex>. А если для некоторого слова не из <tex>\mathrm{L}</tex> в <tex> G </tex> существует путь из <tex> s </tex> в <tex> t </tex>, то он соответствует некоторой корректной последовательности переходов в изначальной машине, таким образом слово должно было приниматься этой недетерминированной машиной.<br />
<br />
Такое построение графа <tex> G </tex> по данной машине Тьюринга можно выполнить с использованием конечного числа переменных, которые будут перебирать всевозможные мгновенные состояния машины (их <tex> O(poly(n)) </tex>, потому переменная, перебирающая его занимает <tex> O(\log n) </tex> памяти), переходы из него и проверка возможности перехода.<br />
<br />
}}<br />
<br />
<br />
<br />
==Теорема Иммермана==<br />
{{ Теорема<br />
| statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex><br />
| proof = <br />
Решим задачу <tex>\mathrm{NCONN} = \{\langle G, s, t \rangle</tex> : в графе G нет пути из s в t<tex>\}</tex>. Очевидно, что этот язык является дополнением языка <tex>\mathrm{CONN}</tex>.<br />
Чтобы показать, что <tex>\mathrm{NCONN}\in \mathrm{NL}</tex>, придумаем недетерминированый алгоритм, использующий <tex>O(\log |G|)</tex> памяти, который проверяет, достижима ли вершина <tex>t</tex> из <tex>s</tex>.<br />
<br />
Определим <tex>R_i</tex> = {<tex>v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.<br />
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.<br />
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.<br />
Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.<br />
{{Лемма<br />
| statement = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.<br />
| proof = <br />
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.<br />
'''Enum'''(<tex>s, i, ri, G</tex>)<br />
<tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов<br />
'''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа<br />
'''continue''' or find path //недетерминированно угадываем путь из s до v или переходим к следующей вершине<br />
<tex>counter</tex>++<br />
'''return'''' <tex>v</tex> //выдаем вершину, до которой угадали путь<br />
'''if''' (<tex>counter \geq r_i</tex>) //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу<br />
'''accept'''<br />
'''reject''' //не нашли <tex>r_i</tex> вершин, не допускаем<br />
<br />
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.<br />
Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.<br />
Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. <br />
'''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск.<br />
<br />
Теперь, имея '''Enum''', можно по индукции находить <tex>r_i</tex>. <br />
Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину — <tex>s</tex>. <br />
Пусть известно значение <tex>r_i</tex>. <br />
Напишем программу, которая на логарифмической памяти будет находить <tex>r_{i + 1}</tex>.<br />
<br />
<br />
'''Next'''(<tex>s, i, r_i, G</tex>)<br />
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r \in R_{i+1}</tex><br />
'''for''' <tex>v = 1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex><br />
'''for''' <tex>u : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex><br />
'''if''' (<tex>u</tex> '''in''' '''Enum'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex><br />
<tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата<br />
'''break''' <br />
'''return''' <tex>r</tex><br />
<br />
<br />
Данный алгоритм изначально учитывает <tex>s</tex>, а затем перебирает всех возможных кандидатов <tex>v</tex> на попадание в <tex>R_{i + 1}</tex>.<br />
Для каждого из них перебираются все ребра, в него входящие.<br />
Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>.<br />
Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова '''Enum'''.<br />
<br />
Теперь напишем алгоритм, который будет недетерминированно решать задачу <tex>\mathrm{NCONN}</tex> на логарифмической памяти.<br />
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.<br />
Вычисление <tex>r_{n-1}</tex> происходит путем вызова '''Next''' <tex>n - 1</tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.<br />
<br />
<br />
'''NCONN'''(<tex>G, s, t</tex>)<br />
<tex>r_n = 1</tex> //<tex>r_0 = 1</tex><br />
'''for''' <tex>i = 0..n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex><br />
<tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>)<br />
'''if''' (<tex>t1</tex> '''in''' '''Enum'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept'''<br />
'''reject'''<br />
'''else'''<br />
'''accept'''<br />
<br />
Данный алгоритм использует <tex>O(\log |G|)</tex> памяти, так как для хранения <tex>r_n</tex> и <tex>i</tex> необходимо <tex>O(\log |G|)</tex>, и для вызываемых '''Next''' и '''Enum''' необходимо <tex>O(\log |G|)</tex> памяти.<br />
<br />
Таким образом показано, что <tex>\mathrm{NCONN} \in \mathrm{NL}</tex>.<br />
Поскольку <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>, то аналогичным образом <tex>\mathrm{NCONN} \in \mathrm{coNLC}</tex>.<br />
Получаем, что любую задачу из <tex>\mathrm{coNL}</tex> можно свести к задаче из <tex>\mathrm{NL}</tex>, а значит <tex>\mathrm{coNL} \subset \mathrm{NL}</tex>.<br />
Из соображений симметрии <tex>\mathrm{NL} \subset \mathrm{coNL}</tex>, а значит <tex>\mathrm{coNL} = \mathrm{NL}</tex>.<br />
<br />
}}<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=PS-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B0_%D0%B2%D0%B5%D1%80%D0%BD%D1%8B%D1%85_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB_%D1%81_%D0%BA%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D1%80%D0%B0%D0%BC%D0%B8_(TQBF)&diff=22999PS-полнота языка верных булевых формул с кванторами (TQBF)2012-05-31T10:33:43Z<p>109.188.223.77: </p>
<hr />
<div>{{Определение<br />
|definition=<tex>TQBF</tex> расшифровывается как True Quantified Boolean Formula. Это язык верных булевых формул с кванторами.<br />
<tex>TQBF=\{Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex><br />
}}<br />
Чтобы доказать, что <tex>TQBF \in PSPACE-complete</tex>, необходимо показать, что эта задача принадлежит <tex>PSPACE</tex> и что она <tex>PSPACE</tex>-трудная.<br />
{{Лемма<br />
|about=1<br />
|statement=<tex>TQBF \in PSPASE</tex><br />
|proof=Чтобы доказать это, просто приведём программу <tex>solve</tex>, решающую булеву формулу с кванторами на <tex>O(n)</tex> дополнительной памяти и работающую за конечное время.<br />
<tex>solve(Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n))</tex><br />
'''if''' <tex>Q_1 == \forall</tex><br />
'''return''' <tex>solve(Q_2 x_2 \cdots Q_n x_n \phi(0, x_2, \dots, x_n)) \land solve(Q_2 x_2 \cdots Q_n x_n \phi(1, x_2, \dots, x_n))</tex><br />
'''if''' <tex>Q_1 == \exists</tex><br />
'''return''' <tex>solve(Q_2 x_2 \cdots Q_n x_n \phi(0, x_2, \dots, x_n)) \lor solve(Q_2 x_2 \cdots Q_n x_n \phi(1, x_2, \dots, x_n))</tex><br />
Эта программа требует <tex>O(n)</tex> дополнительной памяти для хранения стека рекурсивных вызовов. Максимальная глубина стека — <tex>n</tex>.<br />
}}<br />
{{Лемма<br />
|about=2<br />
|statement=<tex> \forall L \in PS , L \leq_p TQBF</tex><br />
|proof=Рассмотрим какой-то язык <tex>L \in PSPACE</tex>. <br />
Построим функцию <tex>f \colon \forall x \in L \Leftrightarrow f(x) \in TQBF</tex>.<br />
Так как <tex>L \in PSPACE</tex>, то существует какая-то детерминированная машина Тьюринга <tex>M</tex>, которая его распознаёт за полиномиальное от размера входа время.<br />
Пусть <tex>I</tex> — мгновенное описание <tex>M</tex>, тогда выражение <tex>\exists I</tex> обозначает <tex> (\exists x_1) (\exists x_2)\cdots(\exists x_n)</tex>, где <tex>\{x_i\}</tex> — все переменные мгновенного описания <tex>M</tex>. Аналогично выражение <tex> \forall I</tex> обозначает <tex> (\forall x_1) (\forall x_2)\dots(\forall x_n)</tex>. Теперь рассмотрим два мгновенных описание <tex>M: A</tex> и <tex>B</tex>. Напишем рекурсивную функцию <tex>\phi(A, B, t)</tex>, которая будет переводить утверждение <tex>A\vdash^tB</tex> в TQBF за полиномиальное относительно длины входа время. <br />
<br />
<tex>\phi(A, B, t) = \\ (\exists R) (\forall U) (\forall V) \ \{\phi(U, V, t/2) \lor [\neg(A = U \land R = V) \land \neg(R = U \land B = V)]\}</tex> <br />
:Переменые <tex> U </tex> и <tex>V</tex> важно рассмотреть только в двух случаях: когда первое из них стартовое, второе — промежуточное, или первое — промежуточное, а второе — финишное. Поэтому для всех остальных вариантов выражение <tex>[\neg(A = U \land R = V) \land \neg(R = U \land B = V)]</tex> будет истинно. Если <tex>A = U \land R = V</tex> то, чтобы <tex>\phi(A, B, t)</tex> было истинно, необходимо наличие такого мгновенного описания <tex>R</tex>, чтобы было выполненно утверждение: <tex>A\vdash^{t/2}R</tex>. Если <tex>R = U \land B = V</tex> то, нас интересует мгновенное описание <tex>R</tex> такое, что <tex>R\vdash^{t/2}B</tex>.<br />
Заметим, что размер функции <tex>\phi(a, B, t)</tex> равен размеру <tex>\phi(A, B, t/2)</tex> с константной добавкой <tex>(\exists R) (\forall U) (\forall V) \ \{\ * \lor [\neg(A = U \land B = R) \land \neg(A = R \land B = V)]\}</tex> .<br />
Теперь мы можем записать функцию <tex>f(M, w)</tex>, которая будет переводить ДМТ <tex>M</tex> и слово на ленте <tex>w</tex> в <tex>TQBF</tex>.<br />
<br />
<tex>f(M, w) = (\exists I_s) (\exists I_f) (x_{I_s, 0} = start \land x_{I_s, 1} = w[1] \land \dots \land x_{I_s, |w|} = w[|w|]) \land ((\exists i) x_{I_f, i} = finish) \land \phi(Start, Finish, 2^{log_2(c^{1+p(n)}})</tex><br />
<br />
Докажем, что получившаяся булева формула с кванторами удовлетворима тогда и только тогда, когда <tex>w \in L</tex>.<br />
<br />
Если <tex>w \in L</tex>, то стартовое и финишное состояние заданы корректно. Также из стартового состояния можно попасть в финишное за полиномиальное время. <br />
<br />
Если <tex>w \not\in L</tex>, то если мы зададим корректное стартовое состояние, то пути до корректного финишного состояния существовать не может.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A1%D1%8D%D0%B2%D0%B8%D1%87%D0%B0._%D0%A1%D0%BE%D0%B2%D0%BF%D0%B0%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_NPS_%D0%B8_PS&diff=22998Теорема Сэвича. Совпадение классов NPS и PS2012-05-31T10:33:31Z<p>109.188.223.77: </p>
<hr />
<div>=Класс PS=<br />
<br />
== Определение ==<br />
{{Определение <br />
|definition='''Класс''' <tex>\mathrm{PS(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br><br />
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{DSPACE}(p(n)) </tex><br />
}}<br />
<br />
{{Определение <br />
|definition='''Класс''' <tex>\mathrm{NPS(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br><br />
<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in \mathrm{P}} \mathrm{NSPACE}(p(n))</tex><br />
}}<br />
<br />
== Связь класса PS с другими классами теории сложности ==<br />
{{Теорема<br />
|statement =<br />
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.<br />
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement =<br />
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.<br />
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.<br />
}}<br />
<br />
=Теорема Сэвича=<br />
<br />
{{Теорема<br />
|statement =<br />
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br><br />
<br />
То есть, если недетерминированная машина Тьюринга может решить проблему используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.<br />
|proof = <br />
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти).<br />
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.<br />
<br />
Пусть <tex>L \in \mathrm{NSPACE}(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br><br />
Рассмотрим вспомогательную функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</tex> за не более, чем <tex>2^k</tex> переходов:<br />
<br />
'''Reach''' (I, J, k)<br />
'''if''' (k = 0)<br />
'''return''' (I <tex>\vdash</tex> J) or (I = J);<br />
'''else'''<br />
'''for''' (Y) // перебор промежуточных конфигураций<br />
'''if''' Reach(I, Y, k-1) and Reach(Y, J, k-1)<br />
'''return''' true;<br />
'''return''' false;<br />
<br />
Эта функция имеет глубину рекурсии <tex>O(k)</tex>, на каждом уровне рекурсии использует <tex>O(f(n))</tex> памяти для хранения текущих конфигураций.<br />
<br />
Рассмотрим машину Тьюринга <tex>m</tex>, распознающую язык <tex>L</tex>. Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>m</tex> имеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Головка на входной ленте может быть в одной из n позиций и в одной из <tex>f(n)</tex> на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}</tex>.<br />
<br />
Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность к языку <tex>L</tex>:<br />
<br />
'''Check''' (x, L)<br />
'''for''' (T) // перебор конфигураций, которые содержат допускающие состояния<br />
'''if''' Reach(S, T, <tex>\log \left(2^{df(n)}\right)</tex>)<br />
'''return''' true;<br />
'''return''' false;<br />
<br />
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции <tex>Reach</tex>. И если слово не допускается за <tex>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. <br />
В итоге функция <tex>Reach</tex> имеет глубину рекурсии <tex>\log{2}^{df(n)}=O(f(n))</tex>, на каждом уровне рекурсии используется <tex>O(f(n))</tex> памяти. Тогда всего эта функция использует <tex>O(f(n)^2)</tex> памяти.<br />
}}<br />
<br />
==Следствие==<br />
<tex>\mathrm{PS}=\mathrm{NPS}</tex><br />
<br />
=Вывод=<br />
<tex>\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PS} = \mathrm{NPS}</tex>.<br />
<br />
Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.<br />
<br />
<br />
=Источники=<br />
* Michael Sipser. Introduction to the theory of computation.<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9C%D0%B0%D1%85%D1%8D%D0%BD%D0%B8&diff=22997Теорема Махэни2012-05-31T10:33:06Z<p>109.188.223.77: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
<tex>LSAT=\{\langle\phi,y\rangle | \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|about=1<br />
|statement=<tex>LSAT \in \mathrm{NPC}</tex>.<br />
|proof=<br />
#Очевидно, что <tex>LSAT \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).<br />
#Сведём <tex>SAT</tex> к <tex>LSAT</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^{|\phi|}\rangle</tex>, где <tex>|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное. <br />
#*Если <tex>\phi \in SAT</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in LSAT</tex>.<br />
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in LSAT</tex>, то <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in SAT</tex>.<br />
:Таким образом, <tex>SAT \le LSAT</tex>. Но <tex>SAT \in \mathrm{NPC}</tex>, а значит <tex>\forall L \in \mathrm{NP} \; L \le SAT</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \le LSAT</tex>, то есть <tex>LSAT \in \mathrm{NPH}</tex>.<br />
Итого мы доказали, что <tex>LSAT \in \mathrm{NPH}</tex> и <tex>LSAT \in \mathrm{NP}</tex>. Тогда по определению <tex>LSAT \in \mathrm{NPC}</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|about=2<br />
|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in LSAT</tex>.<br />
|proof=<tex>\langle\phi,y\rangle \in LSAT</tex>. Тогда <tex>\exists x: x\le_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in LSAT</tex>.<br />
}}<br />
<br />
<br />
{{Теорема<br />
|author=Махэни<br />
|statement=<br />
<tex>\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}</tex>.<br />
|proof=Пусть <tex>S \in \mathrm{NPC} \cap \mathrm{SPARSE}</tex>.<br />
<br />
Так как <tex>S\in \mathrm{NPC}</tex>, и <tex>LSAT \in \mathrm{NP}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in LSAT \iff f(\langle \phi, y \rangle) \in S</tex>.<br />
<br />
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.<br />
<tex>S\in SPARSE</tex>. Следовательно, <tex>\forall n \; |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином. <br />
<br />
Тогда <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.<br />
<br />
Опишем алгоритм для нахождения лексиграфически минимальной строки <tex>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.<br />
<br />
Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.<br />
<br />
Разобьём текущее множество строк на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>.<br />
<br />
Из леммы (2) мы знаем, что, начиная с некоторого <tex>l</tex>, все пары <tex>\langle\phi, w_l\rangle \in LSAT</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge l</tex>.<br />
<br />
Рассмотрим два случая:<br />
<br />
# <tex>\exists i \ne j \, z_i=z_j</tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Тогда по вышеуказанной причине <tex>x\notin (w_i, w_j]</tex>. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac 1{r+1}</tex> часть множества подстановок.<br />
# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>z_0</tex> или <tex>z_1</tex> лежат в <tex>S</tex>, то все последующие <tex>z_i</tex> тоже лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит <tex>r+1</tex> строку длины не более, чем <tex>q(|\phi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.<br />
<br />
В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера. <br />
<br />
Будем повторять эту процедуру до тех пор, пока не останется не более <tex>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формулу <tex>\phi</tex>, то <tex>x=min(w_i), w_i</tex> удовлетворяет <tex>\phi</tex>. Иначе, <tex>x</tex> не существует.<br />
<br />
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n(1-\frac1{r+1})^k</tex> строк. Оценим <tex>k</tex>.<br />
<br />
<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [http://ru.wikipedia.org/wiki/Ряд_Тейлора#.D0.A0.D1.8F.D0.B4.D1.8B_.D0.9C.D0.B0.D0.BA.D0.BB.D0.BE.D1.80.D0.B5.D0.BD.D0.B0_.D0.BD.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9 формулой Тейлора] для логарифма). <br />
<br />
Таким образом, мы можем разрешить язык <tex>LSAT</tex> за полиномиальное время, найдя лексиграфически минимальную строку, удовлетворяющую формулу, и сравнив её с нашим аргументом. Так как <tex>LSAT\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.<br />
<br />
}}<br />
<br />
== См. также ==<br />
*[[Класс P]]<br />
*[[Недетерминированные вычисления. Классы NP и Σ₁]]<br />
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%91%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%BE%D1%80%D1%87%D1%83%D0%BD%D0%B0&diff=22996Теорема Бермана — Форчуна2012-05-31T10:32:52Z<p>109.188.223.77: </p>
<hr />
<div>{{Лемма<br />
|about=1<br />
|statement=<tex>L \in coNPC \Leftrightarrow \overline L \in NPC</tex><br />
|proof=Пусть <tex>L \in coNPC</tex>. Тогда <tex>L \in coNP</tex> и <tex>\overline L \in NP</tex>.<br />
<br />
Рассмотрим произвольный язык <tex>L_1 \in NP</tex>. Тогда <tex>\overline {L_1} \in coNP</tex>. Так как <tex>L \in coNPC</tex>, то <tex>\overline {L_1} \le L</tex>, следовательно <tex>L_1 \le \overline L</tex> (по [[Сведение по Карпу. Трудные и полные задачи|лемме]]).<br />
<br />
Получили, что <tex>\overline L \in NP</tex> и <tex>\forall L_1 \in NP \Rightarrow L_1 \le \overline L</tex>. Значит <tex>\overline L \in NPC</tex>.<br />
В обратную сторону доказательство аналогично.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
<tex>TAUT = \{\phi</tex> {{---}} булева формула <tex>| \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|about=2<br />
|statement=<tex>TAUT \in coNPC</tex><br />
|proof=<tex>\overline {TAUT} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}</tex>, то есть <tex>\overline {TAUT} \in NPC</tex>. Тогда по лемме (1) <tex>TAUT \in coNPC</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
<tex>SPARSE = \{L | \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<tex>coNPC \cap SPARSE \ne \varnothing \Rightarrow P = NP</tex><br />
|proof=Пусть существует <tex>S \in coNPC \cap SPARSE</tex>. Разрешим <tex>TAUT</tex> за полином.<br />
<br />
Для начала напишем программу, разрешающую <tex>TAUT</tex>:<br />
<tex>check(\phi, i)</tex><br />
'''if''' <tex>memo[\phi] \ne -1</tex><br />
'''return''' <tex>memo[\phi]</tex><br />
'''if''' <tex>\phi=0</tex><br />
'''return''' 0<br />
'''if''' <tex>\phi=1</tex><br />
'''return''' 1<br />
<tex>memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex><br />
'''return''' <tex>memo[\phi]</tex> <br />
Ответом будет <tex>check(\phi, 1)</tex>.<br />
<br />
Так как <tex>TAUT \in coNPC</tex> и <tex>S \in coNPC</tex>, то <tex>TAUT \le S</tex>, то есть <tex>\exists f \in \widetilde{P} : \phi \in TAUT \Leftrightarrow f(\phi) \in S</tex>. Поэтому, если в предыдущей программе заменить все обращения к <tex>memo[\phi]</tex>, на <tex>memo[f(\phi)]</tex>, то полученная программа по-прежнему будет разрешать <tex>TAUT</tex>.<br />
<br />
Оценим необходимый размер <tex>memo</tex>. Можно считать, что <tex>T(f(\phi)) \le q(n)</tex>, где <tex>n = |\phi|</tex>, а <tex>q</tex> {{---}} монотонно возрастающий полином. Тогда <tex>|f(\phi)| \le q(n)</tex>. Так как <tex>S \in SPARSE</tex>, то <tex>|S \cap \Sigma^k| \le p(k)</tex>, где <tex>p</tex> {{---}} полином. Можно считать, что <tex>p</tex> монотонно возрастает. Тогда размер <tex>memo</tex> можно оценить сверху: <tex>memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)</tex>, где <tex>r(n)</tex> {{---}} полином.<br />
<tex>check(\phi, i)</tex><br />
'''if''' <tex>memo[f(\phi)] \ne -1</tex> //(1)<br />
'''return''' <tex>memo[f(\phi)]</tex><br />
'''if''' <tex>\phi=0</tex><br />
'''return''' 0<br />
'''if''' <tex>\phi=1</tex><br />
'''return''' 1<br />
<tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex> //(2)<br />
'''if''' <tex>memo.size() > r(n)</tex><br />
'''exit''' <tex>0</tex><br />
'''return''' <tex>memo[f(\phi)]</tex><br />
Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.<br />
<br />
Рассмотрим произвольный элемент <tex>memo[i]</tex>. Заметим, что условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex> не более одного раза. Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>r(n)</tex> раз. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>r(n)</tex> раз, а значит в дереве не более <tex>r(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot r(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.<br />
<br />
Итого, данная программа разрешает <tex>TAUT</tex> за полиномиальное время. А так как <tex>TAUT \in coNPC</tex>, то <tex>P=coNP</tex>, то есть <tex>coP=coNP</tex>, откуда <tex>P=NP</tex>.<br />
}}<br />
<br />
[[Категория: Теория сложности]]<br />
/tex> {{---}} монотонно возрастающий полином. Тогда</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9B%D0%B5%D0%B2%D0%B8%D0%BD%D0%B0&diff=22995Теорема Левина2012-05-31T10:32:31Z<p>109.188.223.77: </p>
<hr />
<div>{{Теорема<br />
|author=Левин<br />
|statement=<br />
Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определения <tex>\Sigma_1</tex>) отношения <tex>R</tex> существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <tex>p</tex>, сопоставляющая словам из <tex>L</tex> их сертификаты, то есть:<br />
# <tex>x \in L \Leftrightarrow R(x, p(x)) = 1</tex>;<br />
# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что <tex>\forall x \Rightarrow T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.<br />
|proof=<br />
Построим «оптимальную» программу <tex>p(x)</tex>.<br />
<br />
Пронумеруем все программы <tex>p_i</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^k</tex> и не делится на <tex>2^{k+1}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>T(P_k, x) \cdot 2^k</tex> шагов.<br />
<br />
Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, запустим в том же потоке проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу больше ничего не запуская в этом потоке.<br />
<br />
Таким образом, если некоторая программа <tex>p_k</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>(T(p_k,x) + T(R, \langle x,p_k(x) \rangle)) \cdot 2^k</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>(T(p_k,x) + poly(|x|)) \cdot 2^k = 2^k \cdot T(p_k,x) + poly(|x|)</tex>.<br />
}}<br />
<br />
== См. также ==<br />
*[[Класс P]]<br />
*[[Недетерминированные вычисления. Классы NP и Σ₁]]<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9B%D0%B0%D0%B4%D0%BD%D0%B5%D1%80%D0%B0&diff=22994Теорема Ладнера2012-05-31T10:32:14Z<p>109.188.223.77: </p>
<hr />
<div>'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].<br />
<br />
== Доказательство ==<br />
<br />
Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что <tex>\mathrm{NP}</tex>-полный язык (например, <tex>\mathrm{SAT}</tex>) нельзя свести по Карпу к полиномиальному. Будем искать язык <tex>A</tex>, удовлетворяющий следующим условиям:<br />
<br />
# <tex>A \in \mathrm{P}</tex> (что влечёт за собой <tex>\mathrm{SAT} \cap A \in \mathrm{NP}</tex>);<br />
# <tex>\mathrm{SAT} \cap A \not \in \mathrm{P}</tex>;<br />
# <tex>\mathrm{SAT} \not \le \mathrm{SAT} \cap A</tex>.<br />
<br />
Если такой язык существует, то <tex>L = \mathrm{SAT} \cap A</tex> является искомым примером множества<br />
из <tex>\mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>.<br />
<br />
Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex>, причём <tex>T(M_i(x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.<br />
<br />
Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i(x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.<br />
<br />
Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую неубывающую функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что для <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> выполняются три названных свойства.<br />
<br />
=== Построение <tex>g</tex> ===<br />
<br />
Определим <tex>g</tex> рекурсивно. Установим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex>:<br />
<br />
* Если <tex>log_2^{g(n)} n \ge n</tex>, <tex>g(n+1) := g(n)</tex>.<br />
<br />
Иначе <tex> n > log_2^{g(n)} n \ge log_2 n</tex>; значения <tex>g(m)</tex> для <tex>m \le log_2 n</tex> уже известны.<br />
<br />
* <tex>g(n) = 2i</tex>.<br />
for <tex>x</tex>: <tex>|x| \le log_2 n</tex><br />
if <tex>M_i(x)</tex> and (<tex>g(|x|) \% 2 = 1</tex> or <tex>x \not \in \mathrm{SAT})</tex><br />
<tex>g(n+1) := g(n)+1</tex>, return<br />
if <tex>! M_i(x)</tex> and (<tex>g(|x|) \% 2 = 0</tex> and <tex>x \in \mathrm{SAT})</tex><br />
<tex>g(n+1) := g(n)+1</tex>, return<br />
<tex>g(n+1) := g(n)</tex><br />
<br />
* <tex>g(n) = 2i + 1</tex>.<br />
for <tex>x</tex>: <tex>|x| \le log_2 n, |f_i(x)| \le log_2 n</tex><br />
if <tex>x \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 1</tex> or <tex>f_i(x) \not \in \mathrm{SAT})</tex><br />
<tex>g(n+1) := g(n)+1</tex>, return<br />
if <tex>x \not \in \mathrm{SAT}</tex> and (<tex>g(|f_i(x)|) \% 2 = 0</tex> and <tex>f_i(x) \in \mathrm{SAT})</tex><br />
<tex>g(n+1) := g(n)+1</tex>, return<br />
<tex>g(n+1) := g(n)</tex><br />
<br />
Утверждается, что для такой функции <tex>g</tex> язык <tex>A = \{x \in \Sigma^*: g(|x|) \% 2 = 0\}</tex> является искомым.<br />
<br />
=== Корректность алгоритма ===<br />
<br />
Проверим выполнение второго и третьего свойств языка <tex>L = \mathrm{SAT} \cap A</tex>.<br />
<br />
* Пусть <tex>g(n)</tex> не имеет предела при <tex>n \to \infty</tex>. Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <tex>M_i</tex> «ошибается»; аналогично, для любой полиномиальной функции <tex>f_i</tex> существует элемент, на котором <tex>f_i</tex> неверно сводит <tex>\mathrm{SAT}</tex> к <tex>L</tex>. Оба свойства выполнены.<br />
<br />
* Пусть <tex>\lim_{n \to +\infty} g(n) = 2i</tex>. Значит, в нашем множестве существует машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>: <tex>\forall x M_i(x) = (g(|x|) \% 2 = 0 \cap x \in \mathrm{SAT})</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \in \mathrm{P}</tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\mathrm{SAT}</tex> в конечном числе элементов, значит, <tex>\mathrm{SAT} \le L</tex>. Получено противоречие с предположением <tex>\mathrm{P} \neq \mathrm{NP}</tex>.<br />
<br />
* Пусть <tex>\lim_{n \to +\infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i</tex>: <tex>\forall x (x \in SAT) = (g(|f_i(x)|) \% 2 = 0 \cap f_i(x) \in \mathrm{SAT})</tex>. С одной стороны, <tex>\mathrm{SAT} \le L</tex> с помощью <tex>f_i</tex>. С другой стороны, из определения <tex>A</tex> выходит, что язык <tex>L</tex> конечен, значит, <tex>L \in \mathrm{P}</tex>. Снова получено противоречие с предположением.<br />
<br />
Таким образом, при верности предположения <tex>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.<br />
<br />
=== Время работы алгоритма ===<br />
<br />
Проверим первое свойство — полиномиальность языка <tex>A</tex>.<br />
<br />
Пусть <tex>T_g(n)</tex> — время вычисления <tex>g(n)</tex>.<br />
<br />
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.<br />
<br />
Время выполнения шагов составляет:<br />
<br />
* проверка неравенства:<br />
<br />
<tex>T_1(n) \le g(n) T_*(log_2^{g(n)} n, log_2^{g(n)} n)</tex><br />
<br />
<tex>T_1(n) \le c_1 g(n) (log_2 (log_2^{g(n)} n))^2</tex><br />
<br />
<tex>T_1(n) \le c_1 g^3(n) log_2^2 log_2 n</tex><br />
<br />
<tex>T_1(n) \le c_1 n^3 log_2^2 log_2 n</tex><br />
<br />
<tex>T_1(n) \le c_1 n^5</tex>,<br />
<br />
где <tex>T_*(a, b)</tex> — время нахождения произведения чисел <tex>a</tex> и <tex>b</tex><br />
<br />
* <tex>g(n) = 2i</tex>:<br />
<br />
<tex>T_2(n) \le 2^{log_2 n} (T(M_i(x)) + T(g(|x|)) + T(x \in \mathrm{SAT}))</tex><br />
<br />
<tex>T_2(n) \le c_2 n (|x|^i + T_g(|x|) + 2^{|x|}|x|)</tex><br />
<br />
<tex>T_2(n) \le c_2 n (log_2^{i} n + T_g(|x|) + 2^{log_2 n} log_2 n)</tex><br />
<br />
<tex>T_2(n) \le c_2 n (log_2^{g(n)} n + T_g(log_2 n) + n log_2 n)</tex><br />
<br />
<tex>T_2(n) \le c_2 (n^2 + n^2 log_2 n + n T_g(log_2 n))</tex><br />
<br />
<tex>T_2(n) \le c_2 (2n^3 + n T_g(log_2 n))</tex><br />
<br />
* <tex>g(n) = 2i + 1</tex>:<br />
<br />
<tex>T_3(n) \le 2^{log_2 n} (T(x \in \mathrm{SAT}) + T_g(|f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))</tex><br />
<br />
<tex>T_3(n) \le c_3 n (2^{log_2 n} log_2 n + T_g(log_2 n) + 2^{log_2 n} log_2 n)</tex><br />
<br />
<tex>T_3(n) \le c_3 (2n^2 log_2 n + n T_g(log_2 n))</tex><br />
<br />
<tex>T_3(n) \le c_3 (2n^3 + n T_g(log_2 n))</tex><br />
<br />
Таким образом,<br />
<br />
<tex>T_g(n) \le T_g(n-1) + c_1 n^5 + c_2 (2n^3 + n T_g(log_2 n)) + c_3 (2n^3 + n T_g(log_2 n))</tex><br />
<br />
<tex>T_g(n) \le T_g(n-1) + k_1 n^5 + k_2 n T_g(log_2 n)</tex><br />
<br />
Если выписывать полученные значения <tex>g(n)</tex> на ленте машины Тьюринга в порядке возрастания <tex>n</tex>, <tex>T_g(log_2 n)</tex> можно получить за <tex>k_3 (n + log_2 n) \le 2 k_3 n</tex>. Тогда<br />
<br />
<tex>T_g(n) \le T_g(n-1) + k_1 n^5 + 2 k_2 k_3 n^2</tex><br />
<br />
Пусть <tex>T_g(1) = const = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно<br />
<br />
<tex>c (n-1)^6 + k_1 n^5 + 2 k_2 k_3 n^2 \le c n^6</tex><br />
<br />
Тогда, в силу <tex>T_g(1) = d \le c 1^6</tex> и неравенства выше, по индукции легко доказать, что <tex>T_g(n)</tex> ограничено сверху <tex>c n^6</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.<br />
<br />
== Источник ==<br />
* ''William Gasarch, Lance Fortnow''. [http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem]<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%91%D0%B5%D0%B9%D0%BA%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%93%D0%B8%D0%BB%D0%BB%D0%B0_%E2%80%94_%D0%A1%D0%BE%D0%BB%D0%BE%D0%B2%D1%8D%D1%8F&diff=22993Теорема Бейкера — Гилла — Соловэя2012-05-31T10:31:59Z<p>109.188.223.77: </p>
<hr />
<div><br />
==Теорема==<br />
{{ Теорема<br />
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.<br />
| proof = <br />
'''Существование оракула <tex>A</tex>'''<br />
<br />
Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>\mathrm{TQBF}</tex>]].<br />
<br />
<tex><br />
\mathrm{P^{TQBF}} \overset{(1)}{\subseteq}<br />
\mathrm{NP^{TQBF}} \overset{(2)}{\subseteq}<br />
\mathrm{NPS^{TQBF}} \overset{(3)}{=}<br />
\mathrm{PS^{TQBF}} \overset{(4)}{=}<br />
\mathrm{PS} \overset{(5)}{\subseteq}<br />
\mathrm{P^{TQBF}}<br />
\Rightarrow<br />
</tex><br/><br />
<tex>\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>.<br />
<br />
# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>.<br />
# <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>.<br />
# По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.<br />
# <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.<br />
# <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.<br />
<br />
----<br />
<br />
'''Существование оракула <tex>B</tex>'''<br />
<br />
Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow U_B \in \mathrm{NP^B}</tex> (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>. <br />
<br />
Пронумеруем некоторым образом все машины Тьюринга, имеющие доступ к оракулу языка <tex>B</tex>, и рассмотрим получившуюся последовательность <tex>M_i</tex>. Построение множества <tex>B</tex> разделим на счетное число стадий, на каждой из которых множество пополнится конечным числом элементов. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-й стадии было выполнено: <tex>M_i</tex> не разрешает язык <tex>U_B</tex> за время не большее, чем <tex>2^{n-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>.<br />
* 0-я стадия: <tex>B \leftarrow \emptyset </tex>.<br />
* <tex>i</tex>-я стадия. Стадии с 0-й по <tex>(i-1)</tex>-ю пройдены, <tex>B</tex> — конечное множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex> следующим образом:<br />
** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на одной из предудщих стадий, то она сохраняется;<br />
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.<br />
<br />
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием <tex>M_i</tex> не разрешает <tex>U_B</tex> за время <tex>2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:<br />
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^n</tex>;<br />
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Добавим <tex>x</tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.<br />
<br />
Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов. <br />
<br />
Из построения получаем, что никакая машина не может разрешить <tex>U_B</tex> за время <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P_B}</tex>.<br />
<br />
}}<br />
<br />
==Следствия==<br />
<br />
{{ Утверждение<br />
| statement = Методом диагонализации нельзя доказать, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>.<br />
}}<br />
<br />
{{ Утверждение<br />
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно "релятивизоваться", поэтому стандартные техники, например, диагонализация не применима.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D1%83%D0%BA%D0%B0&diff=22992Примеры NP-полных языков. Теорема Кука2012-05-31T10:31:29Z<p>109.188.223.77: </p>
<hr />
<div>{{В разработке}}<br />
<br />
== Введение ==<br />
В этой статье мы рассмотрим класс NP-полных языков {{---}} NPC.<br />
NPC является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс P, <br />
тогда окажется, что P = NP.<br />
<br />
Мы рассмотрим некоторые языки и докажем их NP-полноту. Начнем мы с языка <tex> BH_{1N} </tex>, так как к нему несложно сводятся все языки из NP. <br />
Потом с помощью сведений по Карпу будем сводить уже известные языки из NPC к новым языкам, тем самым доказывая их NP-трудность, а потом и NP-полноту.<br />
Доказательство NP-полноты будет состоять из двух пунктов: доказательство NP-трудности и принадлежности языка классу NP.<br />
<br />
== NP-полнота <tex> BH_{1N} </tex> ==<br />
<tex> BH_{1N} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает 1 за время <tex> T(m, x) \le t </tex>.<br />
<br />
<tex> BH_{1N} = \lbrace \langle m, x, 1^t \rangle | m </tex> {{---}} недерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex><br />
{{Теорема<br />
|statement=<tex> BH_{1N} \in NPC </tex><br />
|proof=<br />
# <tex> BH_{1N} \in NPH </tex><br />
# <tex> BH_{1N} \in NP </tex><br />
}}<br />
<br />
== NP-полнота <tex> SAT </tex> ==<br />
<tex> SAT </tex> {{---}} язык булевых формул, для которых существует подстановка, при которой формула истинна.<br />
<br />
<tex> SAT = \lbrace \varphi\ |\ \exists x : \varphi(x) = 1 \rbrace </tex><br />
{{Теорема<br />
|author=Кук<br />
|statement=<tex> SAT \in NPC </tex><br />
|proof=<br />
# <tex> SAT \in NPH </tex><br />
# <tex> SAT \in NP </tex> <br>Можно написать недетерминированную программу, которая распознает язык SAT. Она будет недетерминированно выбирать подстановку, проверять истинна ли формула при такой подстановке и выдавать ответ.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B0_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9._%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9A%D0%B0%D1%80%D0%BF%D1%83._%D0%A2%D1%80%D1%83%D0%B4%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8&diff=22991Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи2012-05-31T10:31:14Z<p>109.188.223.77: </p>
<hr />
<div>== Определения ==<br />
{{Определение<br />
|definition =<br />
<tex>D</tex> — класс языков, удовлетворяющих некоторым ограничениям; <tex>\widetilde{D}</tex> — класс вычислимых функций, удовлетворяющих тем же ограничениям.<br />
'''Язык <tex>L_1</tex> сводится к языку <tex>L_2</tex> относительно <tex>\widetilde{D}</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br><br />
<tex> (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>.<br />
}}<br />
{{Определение<br />
|definition =<br />
Сведение относительно <tex>\mathrm{\widetilde{P}}</tex> называется '''сведением по Карпу'''.<br />
}}<br />
'''Замечание.''' Часто используется именно сведение по Карпу, поэтому слова «относительно сведения по Карпу» и индекс у символа сведения обычно опускают.<br />
<br />
== Простой пример сведения по Карпу ==<br />
Зададим следующие языки:<br />
* <tex>IND</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%BC_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F независимое множество] размера <tex>k</tex>.<br />
* <tex>CLIQUE</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B8%D0%BA%D0%B0_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) клика] размера <tex>k</tex>.<br />
{{Теорема<br />
|statement= <tex>IND \leq CLIQUE</tex><br />
|proof=<br />
Рассмотрим функцию <tex>f( \langle G, k \rangle ) = \langle \overline{G}, k \rangle</tex>, где <tex>\overline{G}</tex> — [http://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 дополнение графа] <tex>G</tex>. <tex>f</tex> вычислима за линейное время от длины входа, если граф задан в виде матрицы смежности.<br><br />
* (<tex>x \in L_1 \Rightarrow f(x) \in L_2</tex>). Заметим, что, если в <tex>G</tex> было независимое множество размера <tex>k</tex>, то в <tex>\overline{G}</tex> будет клика такого же размера (вершины, которые были в независимом множестве, в <tex>\overline{G}</tex> попарно соединены рёбрами и образуют клику).<br />
* (<tex>x \in L_1 \Leftarrow f(x) \in L_2</tex>). Обратно, если в <tex>\overline{G}</tex> есть клика размера <tex>k</tex>, то в исходном графе было независимое множество размера <tex>k</tex>.<br />
Таким образом, <tex>IND \leq CLIQUE</tex> по определению.<br />
}}<br />
'''Замечание.''' Другие примеры сведения по Карпу приведены в статье, содержащей [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]].<br />
<br />
== Свойства сведения ==<br />
<br />
{{Теорема<br />
|about=о транзитивности<br />
|statement=Сведение по Карпу транзитивно, то есть: <tex> ( L_1 \leq L_2, L_2 \leq L_3 ) \Rightarrow L_1 \leq L_3 </tex>.<br />
|proof=<br />
Пусть <tex>f</tex> и <tex>g</tex> — функции из определения сведения для <tex> L_1 \leq L_2 </tex> и <tex> L_2 \leq L_3 </tex> соответственно. Из определения следует: <tex>x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3</tex>.<br />
<br />
Проверим, что <tex>g(f(x))</tex> вычислима за полиномиальное от <tex>|x|</tex> время.<br/><br />
Действительно, первым делом необходимо вычислить <tex>f(x)</tex>, на это уйдет полином от <tex>|x|</tex> времени.<br/><br />
Кроме того, длина входа <tex>g</tex>, являющегося выводом <tex>f(x)</tex>, тоже полиномиальна, так как за единицу времени может быть выведено не более, чем константное число символов. Значит, вычисление <tex>g(f(x))</tex> также займет времени не более, чем полином от <tex>|x|</tex>.<br />
<br />
Таким образом, полное время работы программы есть сумма полиномов от <tex>|x|</tex> и потому тоже является полиномом от <tex>|x|</tex>.<br />
}}<br />
<br />
{{Лемма<br />
|statement=<tex>(L_1 \leq_{\widetilde{D}} L_2) \Leftrightarrow (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex><br />
|proof=<br />
По определению сведения существует такая функция <tex>f</tex> из класса <tex>\widetilde{D}</tex>, что <tex>x \in L_1 \Leftrightarrow f(x) \in L_2</tex>. Для того, чтобы свести <tex>\overline{L_1}</tex> к <tex>\overline{L_2}</tex> будем использовать ту же функцию <tex>f</tex>.<br><br />
В самом деле: <tex>( x \in L_1 \Leftrightarrow f(x) \in L_2 ) \iff ( \overline{x \in L_1} \Leftrightarrow \overline{f(x) \in L_2} ) </tex> <tex>\iff ( x \in \overline{L_1} \Leftrightarrow f(x) \in \overline{L_2} ) \iff (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>.<br />
}}<br />
<br />
== Определения трудных и сложных задач ==<br />
<br />
{{Определение<br />
|definition =<br />
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> сводится к <tex>L</tex> относительно <tex>\widetilde{D}</tex>:<br><br />
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-полным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения и сам лежит в <tex>C</tex>.<br />
}}<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=22989Класс P2012-05-31T10:30:15Z<p>109.188.223.77: </p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>P = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset P</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P&diff=22988Класс P2012-05-31T10:29:24Z<p>109.188.223.77: </p>
<hr />
<div>== Определение ==<br />
{{Определение<br />
|definition=<br />
'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<br />
<tex>P = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.<br />
}}<br />
<br />
Итого, язык <tex>L</tex> лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:<br />
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;<br />
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.<br />
<br />
== Свойства класса P ==<br />
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>.<br />
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.<br />
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).<br />
<br />
{{Лемма<br />
|statement =<br />
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.<br />
|proof =<br />
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.<br />
<tex>q(w):</tex><br />
<tex>n = |w|</tex><br />
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex><br />
for (<tex>i = 1 \ldots n</tex>)<br />
for (<tex>j \in endPoses</tex>)<br />
if (<tex>p(w[j+1 \ldots i])</tex>) {<br />
if (<tex>i = n</tex>)<br />
return true<br />
<tex>endPoses</tex> <tex>\cup = \{i\}</tex><br />
}<br />
return false<br />
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.<br />
}}<br />
<br />
== Соотношение классов Reg и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.<br />
|proof =<br />
<tex>Reg \subset TS(n, 1) \subset P</tex><br />
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.<br />
}}<br />
<br />
== Соотношение классов CFL и P ==<br />
{{Теорема<br />
|statement =<br />
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.<br />
|proof =<br />
<tex>CFL \subset TS(n^3, n^2) \subset P</tex><br />
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].<br />
}}<br />
<br />
== Примеры задач и языков из P ==<br />
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:<br />
* определение связности графов;<br />
* вычисление наибольшего общего делителя;<br />
* задача линейного программирования;<br />
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref><br />
<br />
<br />
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.<br />
<br />
== Задача равенства P и NP ==<br />
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день. <br />
<br />
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.<br />
<br />
== Ссылки ==<br />
<references/><br />
<br />
[[Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=22987Категория:Теория сложности2012-05-31T10:28:42Z<p>109.188.223.77: Новая страница: «Теория сложности»</p>
<hr />
<div>[[Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B._%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81_%D0%BE%D1%80%D0%B0%D0%BA%D1%83%D0%BB%D0%BE%D0%BC&diff=22986Сложностные классы. Вычисления с оракулом2012-05-31T10:27:21Z<p>109.188.223.77: </p>
<hr />
<div>В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?<br />
<br />
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.<br />
<br />
Для начала введём понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).<br />
{{Определение<br />
|definition=<br />
<tex>DTIME(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Time(p,x) = O(f(n)) \}</tex>.<br />
}}<br />
{{Определение<br />
|definition=<br />
<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Space(p,x) = O(f(n)) \}</tex>.<br />
}}<br />
<br />
Через понятия классов <tex>DSPACE</tex>, <tex>DTIME</tex>, <tex>NSPACE</tex> и <tex>NTIME</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].<br />
<br />
== Вычисление с оракулом ==<br />
{{Определение<br />
|definition=<br />
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x \in A</tex>.<br />
}}<br />
Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>.<br />
Если <tex>A</tex> — множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>.<br />
<br />
[[Категория: Теория сложности]]</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B._%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81_%D0%BE%D1%80%D0%B0%D0%BA%D1%83%D0%BB%D0%BE%D0%BC&diff=22983Сложностные классы. Вычисления с оракулом2012-05-31T10:20:57Z<p>109.188.223.77: </p>
<hr />
<div>В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?<br />
<br />
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.<br />
<br />
Для начала введём понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).<br />
{{Определение<br />
|definition=<br />
<tex>DTIME(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Time(p,x) = O(f(n)) \}</tex>.<br />
}}<br />
{{Определение<br />
|definition=<br />
<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Space(p,x) = O(f(n)) \}</tex>.<br />
}}<br />
<br />
Через понятия классов <tex>DSPACE</tex>, <tex>DTIME</tex>, <tex>NSPACE</tex> и <tex>NTIME</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].<br />
<br />
== Вычисление с оракулом ==<br />
{{Определение<br />
|definition=<br />
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x \in A</tex>.<br />
}}<br />
Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>.<br />
Если <tex>A</tex> — это множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>.</div>109.188.223.77http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B._%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81_%D0%BE%D1%80%D0%B0%D0%BA%D1%83%D0%BB%D0%BE%D0%BC&diff=22982Сложностные классы. Вычисления с оракулом2012-05-31T10:17:38Z<p>109.188.223.77: </p>
<hr />
<div>В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?<br />
<br />
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964) и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.<br />
<br />
Для начала введем понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).<br />
{{Определение<br />
|definition=<br />
<tex>DTIME(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Time(p,x) = O(f(n)) \}</tex>.<br />
}}<br />
{{Определение<br />
|definition=<br />
<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L</tex> и для <tex>\forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Space(p,x) = O(f(n)) \}</tex>.<br />
}}<br />
<br />
Через понятия классов <tex>DSPACE</tex>, <tex>DTIME</tex>, <tex>NSPACE</tex> и <tex>NTIME</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].<br />
<br />
== Вычисление с оракулом ==<br />
{{Определение<br />
|definition=<br />
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex>, верно ли, что <tex>x \in A</tex>.<br />
}}<br />
Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>.<br />
Если <tex>A</tex> — это множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>.</div>109.188.223.77