Вклад участника
2 июня 2010
NP-полнота задачи о независимом множестве
Формулировка
-5
Кубит
Измерение кубитов
+26
Кубит
Измерение кубитов
+113
1 июня 2010
Кубит
Измерение кубитов
+538
Класс PCP
Нет описания правки
+1180
Односторонние функции и псевдослучайные генераторы
Нет описания правки
-13
Односторонние функции и псевдослучайные генераторы
Определение
+374
Односторонние функции и псевдослучайные генераторы
Определения
+25
Односторонние функции и псевдослучайные генераторы
Нет описания правки
+167
Односторонние функции и псевдослучайные генераторы
Теорема
+192
Односторонние функции и псевдослучайные генераторы
Определение
+273
Односторонние функции и псевдослучайные генераторы
Доказательство:
+442
Класс PCP
Нет описания правки
+1088
Односторонние функции и псевдослучайные генераторы
Гипотеза
+28
Теорема Лаутемана
Доказательство
+129
Односторонние функции и псевдослучайные генераторы
Определения
+227
Класс PCP
Новая страница: «==Определение== Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного с…»
Теория сложности (старая трешовая версия)
Нет описания правки
Теоремы о коллапсе полиномиальной иерархии
Доказательство
+9
Теоремы о коллапсе полиномиальной иерархии
Доказательство
+4
31 мая 2010
Теорема Ладнера
Иллюстрация
NL-полнота задачи о достижимости в графе
Доказательство NL-трудности задачи STCON
-4
Преобразование Адамара
Нет описания правки
-44
Преобразование Адамара
Нет описания правки
+2
Преобразование Адамара
Нет описания правки
+92
Преобразование Адамара
Нет описания правки
+465
Квантовый логический элемент CNOT
Нет описания правки
-324
30 мая 2010
NP-полнота задачи о рюкзаке
Нет описания правки
-2
NP-полнота задачи о вершинном покрытии
Нет описания правки
+14
NP-полнота задачи BH1N
Нет описания правки
+1
29 мая 2010
Теорема Кука
Доказательство того, что SAT ∈ NPH
NP-полнота задачи BH1N
Доказательство принадлежности BH1N классу NP
+37
NP-полнота задачи BH1N
Доказательство принадлежности BH1N классу NP
+4
NP-полнота задачи BH1N
Определение языка BH1N
-1
Класс P
Задача равенства P и NP
-18
Класс P
Задача равенства P и NP
+1
Класс NP
Класс \Sigma_1
+1
Обсуждение:Теорема о ёмкостной иерархии
Нет описания правки
+1
Обсуждение:Теорема о ёмкостной иерархии
Новая страница: «"Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>." Отсюда следует, что п…»
Теорема о временной иерархии
Доказательство
-45
28 мая 2010
Вероятностная машина Тьюринга
Нет описания правки
+91
Вероятностная машина Тьюринга
Нет описания правки
-42
Односторонние функции и псевдослучайные генераторы
Определение
+23
Односторонние функции и псевдослучайные генераторы
Определение
+21
Односторонние функции и псевдослучайные генераторы
Определение
+10
27 мая 2010
Односторонние функции и псевдослучайные генераторы
Без доказательства
+1
Односторонние функции и псевдослучайные генераторы
Нет описания правки
+1763
Односторонние функции и псевдослучайные генераторы
Новая страница: «=== Односторонние функции === == Определения == * Функция <tex> \epsilon(n) </tex> называется ''пренебрежи…»
Теория сложности (старая трешовая версия)
Лекция 11
+102
Доказательства с нулевым разглашением
Нет описания правки
+16
