54
правки
Изменения
Страницы, описание времени работы
===Доказательство принадлежности NP===
В качестве сертификата возьмем удовлетворяющее условию задачи множество <math>S'</math> с суммой <math>s</math>. Оно удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция проверит вхождение всех элементов <math>S'</math> в множество <math>S</math> за время <math>\left\vert{S'}\right\vert \times \left\vert{S}\right\vert</math>.
===Доказательство принадлежности к NPH===
Сведем [[NP-полнота_задачи_о_выполнимости_булевой_формулы_в_форме_3-КНФ|3-CNF_Sat]] к задаче о сумме подмножества. Пусть задана 3-CNF формула <math>\varphi</math> от <math>n</math>
переменных <math>x_{i}</math>, состоящая из <math>k</math> пар скобок <math>C_{i}</math>. Будем считать, не умаляя общности, что ни одна пара скобок не содержит одновременно переменную и ее отрицание. Также предположим, что каждая переменная входит хотя бы в одну пару скобок. Построим сводящую функцию <math>f\!\!:\varphi \to (S,s)</math>.
==Источники информации==
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms, 3rd Edition" {{---}} Издательство MIT Press, 2009. {{---}} 1292 с1086 c. {{---}} ISBN 978-0-262-03384-8 (англ.)* Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. {{---}} М.: Издательский дом "Вильямс", 2002. {{---}} 528 423 с. {{---}} ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория сложности]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
[[Категория: Примеры NP-полных языков]]
