Вклад участника
6 мая 2010
Класс IP
Определение
+6
Класс IP
Определение
+2
Класс IP
Определение
Класс IP
Определение
+18
Класс IP
Определение
-293
Класс IP
Определение
Класс IP
Определение
+7
Класс IP
Определение
+577
GNI
Нет описания правки
+2
5 мая 2010
GNI
Нет описания правки
+30
GNI
Нет описания правки
+11
GNI
Новая страница: «=== Определение === Проблема '''GNI''' = <tex>\{\langle G_1, G_2\rangle : G_1</tex> неизоморфен <tex>G_2\}</tex> == Формулиро…»
Теория сложности (старая трешовая версия)
Лекция 9
+75
4 мая 2010
3 мая 2010
Теорема Валианта-Вазирани
Вероятность существования единственного удовлетворяющего набора
+6
Теорема Валианта-Вазирани
Нет описания правки
+289
Понятие NP-трудной и NP-полной задачи
Нет описания правки
-20
Понятие NP-трудной и NP-полной задачи
Определение класса NP-трудных задач
-26
Теорема Валианта-Вазирани
Новая страница: «Теорема Валианта-Вазирани (Valiant–Vazirani) является клевым результатом в теории вычислимости. …»
22 апреля 2010
Теорема о включении BPP в P/poly
Доказательство
+320
Теорема о включении BPP в P/poly
Доказательство
+352
Теорема о включении BPP в P/poly
Доказательство
+866
19 апреля 2010
15 апреля 2010
Теорема Иммермана
Нет описания правки
+6
Теорема Иммермана
Доказательство
+86
Вероятностная машина Тьюринга
Вероятности событий, связанных с машиной Тьюринга
+18
Лемма Шварца-Зиппеля
Нет описания правки
+23
Вероятностная машина Тьюринга
Свойство
-4
Вероятностная машина Тьюринга
Определение
+478
Сложностный класс ZPP
Замечание
-1
Сложностный класс ZPP
Замечание
+2
Теорема о связи вопросов EXP=NEXP и P=NP
Доказательство
+37
Сложностный класс ZPP
Нет описания правки
+228
Теорема о связи вопросов EXP=NEXP и P=NP
Доказательство
+25
Вероятностная машина Тьюринга
Определение
+1
Теорема о связи вопросов EXP=NEXP и P=NP
Доказательство
+33
Вероятностная машина Тьюринга
Определение
-27
Вероятностная машина Тьюринга
Определение
Вероятностная машина Тьюринга
Определение
-6
Вероятностная машина Тьюринга
Свойство
-2
Вероятностная машина Тьюринга
Определение
+53
Теорема о связи вопросов EXP=NEXP и P=NP
Нет описания правки
+99
Сложностный класс PP
Определение класса PP
+4
Вероятностная машина Тьюринга
Определение
-175
Вероятностная машина Тьюринга
Определение
+45
BPP
Перенаправление на Сложностный класс BPP
Вероятностная машина Тьюринга
Определение
+238
PP
Перенаправление на Сложностный класс PP
Сложностный класс ZPP
Доказательство
+30
