Вклад участника
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
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+45
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+489
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-1
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-1
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+133
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+255
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+8
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
-6
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+532
NP-полнота задачи о рюкзаке
Нет описания правки
+17
NP-полнота задачи о рюкзаке
описание сведения
+300
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Доказательство принадлежности 3SAT классу NPH
+12
18 марта 2010
Теорема Кука
Доказательство того, что SAT ∈ NPH
-1
Теорема о ёмкостной иерархии
Доказательство
+34
Теорема о ёмкостной иерархии
Доказательство
+126
Теорема о ёмкостной иерархии
Доказательство
+219
Теорема о ёмкостной иерархии
Доказательство
-1
Конструируемая по памяти функция
Определение
-24
Теорема о ёмкостной иерархии
Доказательство
+87
