editor
177
правок
Изменения
м
\mathrm{}
{{Определение
|definition =
Сведение относительно <tex>\mathrm{\widetilde{P}}</tex> называется '''сведением по Карпу'''.
}}
'''Замечание.''' Часто используется именно сведение по Карпу, поэтому слова «относительно сведения по Карпу» и индекс у символа сведения обычно опускают.
Таким образом, <tex>IND \leq CLIQUE</tex> по определению.
}}
'''Замечание.''' Другие примеры сведения по Карпу приведены в статье, содержащей [[Примеры NP-полных языков. Теорема Кука | примеры <tex>\mathrm{NP}</tex>-полных языков]].
== Свойства сведения ==
