41
правка
Изменения
→Примеры #P-Complete задач
== Примеры #P-Complete задач ==
*[[#SAT]]
*Посчитать количество возможных подстановок, удовлетворяющих назначений для которых заданная заданной в ДНФ формула будет удовлетворенаформулы.
*Посчитать количество полных паросочетаний в данном двудольном графе.
*Посчитать количество способов раскрасить заданный граф в <tex>k</tex> цветов.
