54
правки
Изменения
м
Источники информации
Тогда набору значений <math>Y = (0,0,0,1):~ \phi(Y) = 1</math> соответствует <math>S' = \{w_{1},~w_{2},~w_{3},~v_{4},~d_{1},~e_{1},~e_{2}\}</math>. И действительно, <math>100001 + 10000 + 1010 + 101 + 10 + 20 + 2 = 111144</math>.
==Источники информации==
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Introduction to Algorithms, 3rd Edition" {{---}} Издательство MIT Press, 2009. {{---}} 1292 с. {{---}} ISBN 978-0-262-03384-8 (англ.)
* Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. {{---}} М.: Издательский дом "Вильямс", 2002. {{---}} 528 с. {{---}} ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория сложности]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
[[Категория: Примеры NP-полных языков]]
