Вклад участника
31 мая 2010
Преобразование Адамара
Нет описания правки
+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
Доказательства с нулевым разглашением
Нет описания правки
+1793
Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
+80
Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
+912
Кубит
Измерение кубитов
+32
Кубит
Измерение n-кубита
-75
Кубит
n-кубит
-8
Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Доказательство
+16
Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
Кубит
Кубит
-183
Доказательства с нулевым разглашением
Нет описания правки
+151
Кубит
Нет описания правки
-1
Кубит
Нет описания правки
+7
Кубит
Нет описания правки
-3
26 мая 2010
Квантовая схема
Нет описания правки
+277
Квантовый логический элемент Тоффоли
Нет описания правки
+201
Преобразование Адамара
Нет описания правки
-197
Квантовый логический элемент CNOT
Нет описания правки
+3
Преобразование Адамара
Нет описания правки
+163
Преобразование Адамара
Нет описания правки
+132
Квантовая схема
Нет описания правки
+642
Квантовая схема
создание страницы