Викиконспекты - Вклад участника [ru]

Участник:Ulyantsev

2010-06-03T08:11:38Z

Perovskaya: Новая страница: «Вова, блин! Что за фигню ты сделал из оглавления?! !"№;%:?*(»

Вова, блин!
Что за фигню ты сделал из оглавления?!
!"№;%:?*(

Шифр Вернама (одноразовый блокнот)

2010-05-27T13:36:16Z

Perovskaya:

Шифр Вернама (одноразовый блокнот) - единственный известный абсолютно секретный шифр. Он основан на том, что сообщение кодируется побитовым ''xor'' с одноразовым ключом, длина которого не меньше длины передаваемого сообщения.

<tex>E_k(x_1) = x_1 \oplus k</tex>

<tex>D_k(x_1 \oplus k \oplus k) = x_1</tex>

Шифр назван в честь телеграфиста Гильберта Вернама, который сконструировал телеграфный аппарат, автоматически кодирующий сообщения таким методом (ключ подавался на отдельной ленте).

Легко заметить, что нельзя использовать один и тот же ключ несколько раз - при кодировании одинаковых сообщений с одинаковым ключом, полученные сообщения также будут одинаковыми, что позволит анализировать передаваемые сообщения.

Доказательство абсолютной секретности:

Пусть кодируемое слово -- <tex>x</tex>, ключ <tex>k</tex>, результат кодирования <tex> y = x \oplus k </tex>. Таким образом <tex>P(y=y_0) = P(k = y_o \oplus x)</tex>.
Заметим, что при фиксированном <tex>x</tex>, каждому случайному <tex>k</tex> соответствует ровно один <tex>y</tex>, а значит и распределение <tex>y</tex> будет совпадать с распределением ключа, из чего следует, что <tex>\forall x_1 \neq x_2</tex> <tex> f(y_1 \oplus k) = f(y_2 \oplus k)</tex>, что и требовалось доказать.

2010-03-18T15:53:41Z

Perovskaya:

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <tex>f</tex> и <tex>g</tex> таких, что <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, выполняется <tex>DSPACE(g(n)) \ne DSPACE(f(n))</tex>.

== Доказательство ==
Зафиксируем <tex>f</tex> и <tex>g</tex>.

Рассмотрим язык <tex>L = \{ \langle m,x \rangle \mid m(\langle m,x \rangle )</tex> не допускает, используя не более <tex> f(|\langle m,x\rangle|)</tex> памяти <tex>\}</tex> .

Пусть <tex>L \in DSPACE(f)</tex>, тогда для него есть машина Тьюринга <tex>m_0</tex> такая, что <tex>L(m_0)=L</tex>.

Рассмотрим <tex>m_0(\langle m_0,x\rangle)</tex>.

Пусть <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>. Тогда <tex>\langle m_0,x\rangle \in L</tex>, но в <tex>L</tex> по определению не может быть пары <tex>\langle m,x\rangle</tex>, которую допускает <tex>m</tex>. Таким образом, получаем противоречие.

Если <tex>m_0</tex> не допускает <tex>\langle m_0,x\rangle</tex>, то <tex>\langle m_0,x\rangle</tex> не принадлежит языку <tex>L</tex>. Это значит, что либо <tex>m_0</tex> допускает <tex>\langle m_0,x\rangle</tex>, либо не допускает, используя памяти больше <tex>f(|\langle m_0,x\rangle|)</tex>. Но <tex>m_0</tex> выбрана таким образом, что на любом входе <tex>x</tex> она использует не более <tex>f(|x|)</tex> памяти. Получаем противоречие.

Следовательно, такой машины не существует. Таким образом, <tex>L \notin DSPACE(f)</tex>.

<tex>L \in DSPACE(g)</tex>, так как можно представить машину Тьюринга <tex>m_0</tex>, распознающую <tex>L</tex>. На любом входе <tex>\langle m_1,x\rangle \in L</tex> <tex>m_0</tex> будет работать аналогично <tex>m_1</tex>. Если <tex>m_1</tex> завершила работу, используя не более <tex>f(|\langle m_1,x\rangle|)</tex> памяти, и не допустила, то <tex>m_0</tex> допускает <tex>\langle m_1,x\rangle</tex>. В другом случае не допускает. Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>. <tex> \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0</tex>, поэтому начиная с некоторого <tex>n</tex>, <tex>m_1</tex> будет использовать памяти не более <tex>g(|\langle m_1,x\rangle|)</tex>.

Получается, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \emptyset</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>

Теорема доказана.

Класс co-NP

2010-03-18T15:51:46Z

Perovskaya:

В теории сложности '''Класс''' <tex>coNP</tex> — класс языков (задач), дополнение к которым является NP.

<tex>coNP = \Pi_1</tex> (См. [[Полиномиальная иерархия]])

==Теоремы, связанные с coNP==
Если <tex>NP \ne coNP</tex>, тогда <tex>P \neq NP</tex>

==Пример задач класса coNP==
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT

2010-03-18T15:07:13Z

Perovskaya:

В теории сложности '''Класс''' <tex>NP</tex> - класс языков (задач), ответ на которые можно проверить за полиномиальное время.

===Определение===
Определение класса NP через [[Класс NTIME|класс NTIME]] и [[Класс NSPACE|класс NSPACE]].

<tex>NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)</tex>

===Класс <tex>\Sigma_1</tex>===
Альтернативным определением класса NP является определение на языке сертификатов.
Классом <tex>\Sigma_1</tex> называется класс языков (задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат (утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.

<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>

==Теорема о равенстве <tex>\Sigma_1 </tex> и <tex> NP</tex>==
===Формулировка===
<tex>\Sigma_1 = NP</tex>
===Доказательство===
Построим доказательство равенство из доказательств двух взаимных включений.

<tex>\Sigma_1 \subset NP</tex>

Построим программу, работающую за полином (из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в <tex>NP</tex>.

Вхождение доказано.

<tex>NP \subset \Sigma_1</tex>

Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.

Теорема доказана.

==Теорема о равенстве <tex>\Pi_1 </tex> и <tex> NP</tex>==
<tex>NP = \Pi_1</tex>

==Примеры задач класса NP==
* Задача о нахождении независимого множества заданного размера в графе. IND
* Задача о нахождении клики заданного размера в графе. CLIQUE
* Задача о нахождении вершинного покрытия заданного размера в графе. COVER
* Задача о удовлетворении булевой формулы, заданной в КНФ. SAT