130
правок
Изменения
→Примеры языков из co-NP
== Примеры языков из co-NP ==
* Даны <tex>n</tex> целых чисел. Верно ли, что любое их непустое подмножество имеет ненулевую сумму?
* TAUT: определить, является ли заданная булева формула тавтологией. К этой задаче легко тривиально сводится дополнение к SAT: если отрицание формулы выполнимоневыполнимо, то она не является тавтологией, и наоборот.
== Связь P и NP ==
