Первое понимание того, что значит быть в NP, может быть полезным.По сути, проблема в NP, то есть весь класс проблем решения, когда при наличии сертификата ответ «да» может быть полностью проверен за полиномиальное время.Если разбить этот вопрос на несколько частей, это может доказать, что проблема в этом примере является NP-полной.Нет вопросов.Пример: Учитывая N человек и S наборов, существует ли число k, которое представляет минимальное количество людей, которое должно быть в каждом наборе S, так что каждый набор завершен.
Предоставьте сертификат: Дайте общее"обоснованное предположение" для данного решения проблемы.Пример: набор размера k
Сформулируйте проверку сертификата за полиномиальное время: Придумайте способ, которым ответ на проблему можно проверить за полиномиальное время (O (n ^ 2), O (n) и т. Д.).Пример: Просмотрите каждый набор S и добавьте к массиву, если он квалифицируется как «некоторое условие», если он добавляет к множеству, и продолжите для всех N. Когда закончите, найдите размер созданного набора.Эта проверка занимает полиномиальное время.
Для упомянутой проблемы попробуйте разбить проблему на эти шаги и, возможно, для проверки используйте популярные алгоритмы, чтобы попытаться найти возможный ответ.Также важно добавить некоторый тип проверки существования на шаге 3. Проверка, действительно ли G является графом с вершинами V и ребрами E, было бы полезно для этого доказательства.