Вклад участника
2 июня 2010
Теория сложности (старая трешовая версия)
Лекция 1. Вводная
-19
Теорема Карпа-Липтона
Нет описания правки
+1549
Теорема Карпа-Липтона
Нет описания правки
+1283
Редкие языки
Новая страница: «Язык <tex>L</tex> - редкий, если <tex> | L \cap \Sigma^n | \le p(n)</tex>. ==Теорема (Махэни)== <tex>NP \le L,~L\in Sparce \Rightarrow P …»
Теория сложности (старая трешовая версия)
Лекция 4
+29
Схемная сложность
Нет описания правки
+3
P/poly
Новая страница: «<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»
Теория сложности (старая трешовая версия)
Лекция 4
-10
Класс 'P\poly'
Новая страница: «<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»
Теория сложности (старая трешовая версия)
Лекция 4
-4
Теория сложности (старая трешовая версия)
Лекция 4
+17
P\poly
Новая страница: «<b><i>P\poly </i></b><tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex> ==Альтернативное определе…»
Схемная сложность
Новая страница: «Пусть <tex>\Sigma = \{0, 1\}</tex>.<br> Тогда язык <tex>L</tex> имеет <i>схемную сложность</i> <tex>f(n)</tex>, если <tex>\exi…»
Теорема Карпа-Липтона
Нет описания правки
+1407
Теория сложности (старая трешовая версия)
Нет описания правки
+71
ЭПР парадокс
<tex> -> </tex>
+1
Теорема Карпа-Липтона
Нет описания правки
+386
Сложностный класс ZPP
Определения
-2
Теорема Карпа-Липтона
Нет описания правки
+2
Теорема Карпа-Липтона
Нет описания правки
-26
Теорема Карпа-Липтона
Нет описания правки
+26
Теорема Карпа-Липтона
Нет описания правки
-8
Теорема Иммермана
Утверждение теоремы
+34
Класс IP
Определение
+12
Теория сложности (старая трешовая версия)
Отмена правки 1338 участника 192.168.0.2 (обсуждение)
-24
Теория сложности (старая трешовая версия)
Практика 6
+24
Классы Sigma i и Pi i
Нет описания правки
+67
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
