Вклад участника
4 апреля 2010
Полиномиальная иерархия
Нет описания правки
+1120
Класс PH
Новая страница: «Классом сложности <math>PH</math> (англ. polynomial hierarchy) называется объединение классов сложности из…»
Теория сложности (старая трешовая версия)
Практика 6
+20
1 апреля 2010
PS-полнота задачи Generalized geography
Нет описания правки
+156
PS-полнота задачи Generalized geography
small fix
+180
PS-полнота задачи Generalized geography
Доказательство принадлежности задачи классу PSH
+13
30 марта 2010
PS-полнота задачи Generalized geography
рис1, 2, 3.
+65
Теоремы о коллапсе полиномиальной иерархии
Нет описания правки
+1762
Теоремы о коллапсе полиномиальной иерархии
Нет описания правки
+6
Теоремы о коллапсе полиномиальной иерархии
Доказательство
+126
Теоремы о коллапсе полиномиальной иерархии
Новая страница: «== Утверждение теоремы == Если <math>\Sigma_i = \Sigma_{i+1}</math>, то <math>\Sigma_i = PH</math>. == Доказательство == Из …»
Теория сложности (старая трешовая версия)
Практика 6
+86
Полиномиальная иерархия
Нет описания правки
-37
Полиномиальная иерархия
Новая страница: «Полиномиальной иерархией называется класс <math>PH = \cup_{n=0}^{\infty} \Sigma_n</math>. ---- См. Классы Sigma_i»
Теория сложности (старая трешовая версия)
Практика 6
-28
Теория сложности (старая трешовая версия)
Практика 6
+77
Теория сложности (старая трешовая версия)
Нет описания правки
+51
Теория сложности (старая трешовая версия)
Практика 6
+26
20 марта 2010
19 марта 2010
NP-полнота задач о гамильтоновом цикле и пути в графах
Доказательство принадлежности к NPH
+241
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-7
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Доказательство принадлежности классу NPH
-11
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Доказательство принадлежности классу NPH
+76
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Доказательство принадлежности классу NPH
+336
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Доказательство принадлежности классу NPH
+25
Теорема Кука
Нет описания правки
+167
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Доказательство принадлежности классу NP
-11
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Теорема
-47
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Теорема
+16
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Теорема
+2
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Теорема
+26
Теорема Кука
Нет описания правки
+91
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Нет описания правки
+70
Теорема Ладнера
Доказательство
+5
Теорема Кука
Доказательство того, что SAT ∈ NPH
+15
Теорема Кука
Нет описания правки
+545
NP-полнота задачи о раскраске графа
Нет описания правки
+21
NP-полнота задачи о раскраске графа
Нет описания правки
+1
NP-полнота задачи о раскраске графа
Нет описания правки
+13
NP-полнота задачи о раскраске графа
Нет описания правки
+48
NP-полнота задачи о раскраске графа
s/math/tex/g
-20
Теорема Левина
Нет описания правки
-34
NP-полнота задачи о раскраске графа
Нет описания правки
+22
NP-полнота задачи о независимом множестве
Формулировка
+1
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-1
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-12
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+161
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+27
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+314
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-1
