3622
правки
Изменения
→Примеры NP-полных языков: пополнен раздел примеров
=== [[Примеры NP-полных языков]] ===
=== 3. [[Примеры NP-полных языков]] ===
* [[NP-полнота языка CNFSAT]]
* [[NP-полнота языка 3SAT]]
* [[NP-полнота языка IND (максимальное независимое множество)]]
* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]
* [[NP-полнота языка FACTOR]]
* [[NP-полнота языка CLIQUE]]
* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
* [[NP-полнота задачи о сумме подмножества]]
* [[NP-полнота задачи о рюкзаке]]
* [[NP-полнота задачи о раскраске графа]]
=== Сложность по памяти, классы PS, L, NL, coNL ===
