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