Является этой проблемой NP, и это имеет имя?

Эта проблема подошла в реальном мире, но я перевел его в более универсальную "подобную учебнику" формулировку. Я подозреваю, что это - NP, но я особенно интересуюсь знанием, если это имеет имя или известно, так как я думаю, что не могу быть первым, который встретится с ним.;-)

Предположите, что существует сторона еды с гостями N. Каждый гость может принести его "тарелку подписи" стороне, или ничего не принести. Каждый гость или любит или ненавидит каждую из тарелок, которые другие гости могут принести (и это известно заранее, так как они - все старые друзья!), но им всем нравятся их собственные тарелки.

Существует ли детерминированный алгоритм, который не занимает время для нахождения самого маленького набора тарелок, который удовлетворяет ограничение, что все гости найдут по крайней мере одну тарелку к своей симпатии? Я говорю самое маленькое, но на самом деле может быть несколько решений, и я хотел бы знать их всех, если это возможно.

Или более абстрактным способом вообразите квадратную матрицу, где все элементы или 0 или 1, и все диагональные элементы равняются 1. Каковы самые маленькие наборы строк, таким образом, что сумма (или двоичный файл ИЛИ) строк в каждом наборе имеет, не обнуляет? (Строки были бы тарелками, столбцы будут гостями, 1 означал бы, что гостю нравится тарелка, и диагональные элементы 1, так как всем нравится их собственная тарелка.)

Это могло быть обобщено к неквадратным матрицам, или путем удаления diagonal=1 правила (хотя последние гарантии, что всегда будет по крайней мере одно решение). Но я не забочусь о тех случаях на данный момент...

У меня уже есть программа, которая решает его посредством исчерпывающего поиска и достаточно быстра для N приблизительно 20, но это занимает время. Я думаю, что я, возможно, должен повториться к стохастическим алгоритмам для нахождения достаточно хороших решений для больших значений N.

Добавленный

Ничего себе, спасибо за быстрый ответ! "Установило покрытие", это - имя, которое я искал.:)