Теория сложности (старая трешовая версия) — различия между версиями
(→Лекция 4) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 10 промежуточных версий 8 участников) | |||
| Строка 14: | Строка 14: | ||
*[[Теорема о временной иерархии]] утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <tex>f\,\!</tex> и <tex>g\,\!</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0</tex>, выполняется '''DTIME'''(''g''(''n'')) ≠ '''DTIME'''(''f''(''n'')). | *[[Теорема о временной иерархии]] утверждает, что для любых двух [[Конструируемая по времени функция|конструируемых по времени функций]] <tex>f\,\!</tex> и <tex>g\,\!</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0</tex>, выполняется '''DTIME'''(''g''(''n'')) ≠ '''DTIME'''(''f''(''n'')). | ||
| − | Через понятия классов ''' | + | ---- |
| + | |||
| + | Через понятия классов '''DSPACE''', '''DTIME''', '''NSPACE''' и '''NTIME''' будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''. | ||
Класс '''P''' — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально: | Класс '''P''' — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально: | ||
| − | *'''P'''=<tex>\bigcup_{i=0}^{\infty}</tex>''' | + | *'''P'''=<tex>\bigcup_{i=0}^{\infty}</tex>'''DTIME'''<tex>(in^i)</tex> |
В свою очередь, при разрешении языка из класса '''NP''' используется недетерминированная машина: | В свою очередь, при разрешении языка из класса '''NP''' используется недетерминированная машина: | ||
*'''NP'''=<tex>\bigcup_{i=0}^{\infty}</tex> '''NTIME'''<tex>(in^i)</tex> | *'''NP'''=<tex>\bigcup_{i=0}^{\infty}</tex> '''NTIME'''<tex>(in^i)</tex> | ||
| − | Дадим определение класса '''NP''' на языке сертификатов | + | Дадим определение класса '''NP''' на языке сертификатов: |
| − | *'''NP'''=<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex> ( | + | *'''NP'''=<tex>\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}</tex> (первое равенство доказывается в статье '''[[NP]]'''). Поясним, что <tex>y</tex> является сертификатом принадлежности <tex>x</tex> языку <tex>L</tex>, если существует полиномиальное отношение (верификатор) <tex>R</tex>, такое что <tex>R(x,y)=1</tex> тогда и только тогда, когда <tex>x</tex> принадлежит <tex>L</tex>. |
| + | |||
| + | Вместе со многими сложностными классами имеет смысл рассматривать и их дополнения (используется приставка '''co-'''). Например, класс '''[[co-NP]]'''. | ||
| + | |||
| + | ---- | ||
| + | Введем в рассмотрение отношения между языками: [[сведение по Карпу]] и [[сведение по Куку]]. | ||
| + | *Язык <tex>A</tex> сводится по Карпу к языку <tex>B</tex>, если существует функция <tex>f(x)</tex> такая, что <tex>x \in A</tex> тогда и только тогда, когда <tex>f(x) \in B</tex>. | ||
| + | *Язык <tex>A</tex> сводится по Куку к <tex>B</tex>, если существует разрешающая язык <tex>A</tex> программа <tex>m</tex>, работающая полиномиальное время от длины входа, которая может использовать разрешающую программу <tex>m_B</tex> для языка <tex>B</tex> в качестве оракула. При этом время работы <tex>m_B</tex> не учитывается. | ||
| − | + | В дальнейшем чаще будет рассматриваться сведение по Карпу. | |
| − | |||
| − | |||
== Практика 1 == | == Практика 1 == | ||
| Строка 59: | Строка 66: | ||
==Лекция 4== | ==Лекция 4== | ||
*[[Схемная сложность]] | *[[Схемная сложность]] | ||
| − | *[[P | + | *[[P/poly]] |
| + | *[[Редкие языки]] | ||
| + | *[[Теорема Махэни]] | ||
== Лекция 5 == | == Лекция 5 == | ||
| Строка 84: | Строка 93: | ||
== Практика 7 == | == Практика 7 == | ||
*[[Вероятностная машина Тьюринга]] | *[[Вероятностная машина Тьюринга]] | ||
| − | *[[ | + | *[[Сложностный класс ZPP]] |
*[[Сложностные классы RP и coRP]] | *[[Сложностные классы RP и coRP]] | ||
*[[Сложностный класс PP]] | *[[Сложностный класс PP]] | ||
| Строка 106: | Строка 115: | ||
*[[Теорема Шамира]] | *[[Теорема Шамира]] | ||
*[[Семейство универсальных попарно независимых хеш-функций|Семейство универсальных попарно независимых хеш-функций]] | *[[Семейство универсальных попарно независимых хеш-функций|Семейство универсальных попарно независимых хеш-функций]] | ||
| + | *[[Протокол Гольдвассера-Сипсера для оценки размера множества]] | ||
*[[Теорема Голдвассера, Сипсера]] | *[[Теорема Голдвассера, Сипсера]] | ||
Текущая версия на 19:10, 4 сентября 2022
Лекция 1. Вводная
Начнем курс с введения понятий DTIME и DSPACE.
- DTIME(f(n)) = машина Тьюринга , где — длина входа .
- DSPACE(f(n)) = машина Тьюринга .
Аналогичным образом введем классы NSPACE и NTIME, использующие недетерминированную машину Тьюринга взамен детерминированной (в течении всего курса префикс D соответствует детерминизму, а N — недетерминизму).
Рассмотрим и докажем теоремы о емкостной и временной иерархии.
- Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций и таких, что , выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).
- Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций и таких, что , выполняется DTIME(g(n)) ≠ DTIME(f(n)).
Через понятия классов DSPACE, DTIME, NSPACE и NTIME будет дано определение многим сложностным классам, в том числе P и NP.
Класс P — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Формально:
- P=DTIME
В свою очередь, при разрешении языка из класса NP используется недетерминированная машина:
- NP= NTIME
Дадим определение класса NP на языке сертификатов:
- NP= (первое равенство доказывается в статье NP). Поясним, что является сертификатом принадлежности языку , если существует полиномиальное отношение (верификатор) , такое что тогда и только тогда, когда принадлежит .
Вместе со многими сложностными классами имеет смысл рассматривать и их дополнения (используется приставка co-). Например, класс co-NP.
Введем в рассмотрение отношения между языками: сведение по Карпу и сведение по Куку.
- Язык сводится по Карпу к языку , если существует функция такая, что тогда и только тогда, когда .
- Язык сводится по Куку к , если существует разрешающая язык программа , работающая полиномиальное время от длины входа, которая может использовать разрешающую программу для языка в качестве оракула. При этом время работы не учитывается.
В дальнейшем чаще будет рассматриваться сведение по Карпу.
