Изменения

Перейти к: навигация, поиск

Классы Sharp P, Sharp P-Complete

193 байта убрано, 11:51, 29 апреля 2017
→‎Класс #P-Complete
Если <tex>f \in FP </tex>, тогда <tex>FP=FP^f</tex>. Получаем, что, если <tex>f - \#P</tex>-полная и <tex>f \in FP</tex>, то <tex>FP=\#P</tex>.
 
Для множества языков из <tex>NP</tex> (таких как <tex>3SAT, CLIQUE, Ham </tex>) существуют их версии из <tex>\#P</tex>. См. <tex>\#SAT</tex>.
== Примеры #P-полных задач ==
Veda
41
правка
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/60697»

Навигация