Вклад участника
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
24 апреля 2012
18 апреля 2012
15 апреля 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Определение полного языка
+822
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение сложного языка
+570
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Нет описания правки
м+114
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил теорему о транзитивности
+1830
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил пример сведения
+2447
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение
4 апреля 2012
Теория сложности
Добавлены темы первой волны
+1356
Заглавная страница
Разделены старая и новая версия «теории сложности»
м+181
Теория сложности
Убран редирект
-112
Теория сложности
переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.
Теория сложности (старая трешовая версия)
переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.
м
24 января 2012
Автоматы с магазинной памятью
Недетерминированный автомат с магазинной памятью
м-1
Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
Идиотский баг
мНеукорачивающие и контекстно-зависимые грамматики, эквивалентность
Бысрый фикс
м+1
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Эквивалентность двухстековой машины трёхсчётчикой машине
м+44
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Эквивалентность двухстековой машины трёхсчётчикой машине
м+18
Лемма о разрастании для КС-грамматик
Лемма о разрастании для КС-грамматик
м+27