Изменения

* Даны <tex>n</tex> === Дополнение к задаче о сумме подмножеств ===Языком этой задачи являются такие множества целых чисел, что сумма любого их непустого подмножества ненулевая. Верно лиЭтот язык является дополнением языка таких кортежей целых чисел, что любое какое-то их непустое подмножество имеет ненулевую суммуноль, разрешаемого за полиномиальное время следующей программой: <tex>r(S)\colon</tex> <tex>Z \gets?\{ 0, 1 \}^{|S|}</tex> '''if''' <tex>Z = 0^{|S|}</tex> '''or''' <tex>\sum_{i=0}^{|S|} S[i] \cdot Z[i] \ne 0</tex> '''return''' ''false'' '''else''' '''return''' ''true'' * === TAUT: ===Требуется определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к <tex>\mathrm{SAT}</tex>: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.