3622
правки
Изменения
→3. Примеры NP-полных языков
=== 3. [[Примеры NP-полных языков]] ===
# [[NP-полнота языка CNFSAT]] (1)
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
## Оформить правильно
# [[NP-полнота языка 3SAT]] (1)
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
## Оформить правильно
# [[NP-полнота языка IND (максимальное независимое множество)]] (3)
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
## Оформить правильно
## Добавить картинку графа-примера
# [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]] (1)
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
## Оформить правильно
# [[NP-полнота языка FACTOR]] (3)
## Оформить правильно
## Пояснить происходящее
# [[NP-полнота языка CLIQUE]] (2)
## Оформить правильно
## Проинлайнить доказательство
# '''!!!''' [[NP-полнота задач о гамильтоновом цикле и пути в графах]] (7)
## Оформить правильно
## Картинки сделать красивыми
# [[NP-полнота задачи о сумме подмножества]] (3)
## Оформить правильно
# [[NP-полнота задачи о рюкзаке]] (3)
## Оформить правильно
## Пояснить подробней
# [[NP-полнота задачи о раскраске графа]] (2)
## Оформить правильно
=== 4. Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
