Вклад участника
3 июня 2012
Теорема Сэвича. Совпадение классов NPS и PS
Определение
м-12
Теорема Сэвича. Совпадение классов NPS и PS
Теорема Сэвича
м+184
Класс P
Свойства класса P
м+2
Классы BPP
Теорема
м-24
Классы BPP
Теорема
м+12
1 июня 2012
Обсуждение:Теорема о непринадлежности XOR классу AC⁰
ToDo
Теорема о непринадлежности XOR классу AC⁰
Теорема
м+5
31 мая 2012
Класс P
Свойства класса P
м+242
Класс P
Свойства класса P
м+30
Класс P
Свойства класса P
м+60
Схемная сложность и класс P/poly
Определения
м-9
Схемная сложность и класс P/poly
Теоремы
м-55
Схемная сложность и класс P/poly
Определения
м-1
13 мая 2012
Теорема Сэвича. Совпадение классов NPS и PS
Теорема Сэвича
м-54
Теорема Сэвича. Совпадение классов NPS и PS
Связь класса PS с другими классами теории сложности
м-117
Классы NC и AC
Определения
м+34
Теорема Сэвича. Совпадение классов NPS и PS
Определение
м-6
11 мая 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Ещё \mathrm{}
м-20
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
\mathrm{}
м+29
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Свойства сведения
м-436
9 мая 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Свойства сведения
м+169
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Определения трудных и сложных задач
м+60
Теория сложности
Поправлена ссылка на «Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи»
м+71
Сведение по Карпу. Трудные и полные задачи
Убран редирект
-184
Сведение по Карпу. Трудные и полные задачи
переименовал Сведение по Карпу. Трудные и полные задачи в [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные за...
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
переименовал Сведение по Карпу. Трудные и полные задачи в [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные за...
м
8 мая 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Определение сведения
м-22
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил доказательство леммы
+673
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Нет описания правки
м+91
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Банальный пример сведения по Карпу
м+52
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение
+1012
7 мая 2012
Обсуждение:Теорема Сэвича. Совпадение классов NPS и PS
ToDo
Обсуждение:Схемная сложность и класс P/poly
ОГОСПАДЕ ЧТО ЭТО
Теоремы о временной и ёмкостной иерархиях
Убрана очевидность
м-2
Класс P
Задача равенства P и NP
м+83
6 мая 2012
Обсуждение:Теоремы о временной и ёмкостной иерархиях
+1 к todo
м+321
Теоремы о временной и ёмкостной иерархиях
Чуточку подправил читабельность
м+12
Обсуждение:Класс P
Todo №n
+1344
30 апреля 2012
29 апреля 2012
Обсуждение:Класс P
TODO
мОбсуждение:Теоремы о временной и ёмкостной иерархиях
todo
Обсуждение:Класс P
todo
Обсуждение:Теорема Махэни
todo
27 апреля 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Нет описания правки
м+149
Обсуждение:Теорема Бермана — Форчуна
ToDo
+247
Обсуждение:Примеры NP-полных языков. Теорема Кука
Обязательно todo
