Сокращение от / к проблеме клика, чтобы доказать проблему - NP Complete

Question

У меня есть следующая проблема: Учитывая набор мужчин и набор женщин, с рангом между любыми двумя людьми, равным 0 или 1. Выберите подмножество людей так, чтобы:

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

• ВВ выбранном подмножестве людей должно быть равное количество мужчин и женщин.

Мои вопросы: чтобы показать np-полноту этой проблемы, я знаю, что можно использовать сокращение проблемы клики.Кто-нибудь может привести пример, как выполнить это сокращение?Нужно ли мне сокращение от или до проблемы с кликом?Большое спасибо

Answer 1

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

Первый шаг к доказательству того, что проблема является NP-полнойиспользование сокращения - это фактическое доказательство того, что проблема в NP.То есть, проблема может быть проверена за полиномиальное время.

Как вы это делаете? Может ли ваша проблема быть превращена в проблему решения (например, проблема да / нет)Может ли это решение проблемы быть сертифицировано?Есть ли ответ / решение вашей проблемы?Можете ли вы проверить, что сертификат для решения проблемы может быть сделан за полиномиальное время?Если да, то вы доказали, что ваша проблема в NP.

Теперь, когда вы знаете, что проблема в NP, вы можете использовать сокращение, чтобы доказать, что проблема NP-полная или NP-сложная.(Если бы проблема была в NP, то было бы абсолютно бесполезно переходить к шагу сокращения, потому что проблема не может быть NP-полной, если она не в NP.)

Для сокращения вам следует преобразоватьпроблема клики в твою проблему. Как вы это сделаете? Хорошо, подумайте, какие элементы проблемы клики можно превратить в элементы вашей проблемы.В вашей задаче есть мужчины / женщины, но в задаче клика есть узлы / вершины.В вашей задаче есть соединения, равные 0 (не понравившиеся) или 1 (понравившиеся), но в задаче клика есть взвешенные (или невзвешенные ребра).Вы пытаетесь найти подмножество людей с наибольшим количеством лайков между ними, но в проблеме клика вы максимизируете количество вершин в клике.По большей части, это почти похоже на преобразование один-к-одному.Сложная часть вашей проблемы заключается в том, что должно быть четное количество мужчин и женщин.Для этого вам нужно проявить немного творчества и найти способы трансформировать проблему клики.

Как только вы трансформируете задачу из клики в свою проблему, вы можете просто доказать, что ответ на кликупроблема является ответом на вашу проблему и наоборот.

Это структура доказательства того, что проблема NP-трудна.Самая сложная часть - это процесс трансформации.Однако дело в том, что, если вы думаете достаточно глубоко, проблемой клики можно манипулировать, чтобы она превратилась в вашу проблему.

Надеюсь, это поможет!

Answer 2

Чтобы ответить на ваш вопрос, вам нужно уменьшить проблему ОТ клики до проблемы, с которой вы сейчас работаете, поскольку клика - это известная проблема, полная NP.

Что касается ваших подсказок в процессе преобразования (из известныхПроблема Клика к вашей проблеме ранжирования), хороший способ подумать об этом - как бы вы сводили сценарий клики к вашей проблеме.Я предполагаю, что 1 означает «связанные люди», а 0 означает «не понравившиеся люди» в вашей задаче.

Примите каждого человека в качестве нашей вершины в графе G (предполагается, что данный граф в задаче клика).Чтобы провести различие между мужчиной и женщиной, мы бы отметили группу мужчин как A1, A2, A3 ... Am, группу женщин как B1, B2, B3 ... Bf.Теперь мы можем нарисовать ребра для каждой пары людей, чей ранг 1 между ними (понравившиеся люди).Предположим, что N (N> = 1) клик, сформированных после того, как граф сделан.

Теперь мы удаляем вершины в каждой клике, что делает клику неравным числом As и Bs (чтобы обеспечить равное количество вершин в обоих полах).Теперь самая большая клика с номером K - это та, которую вы будете искать.

Предполагается, что это преобразование будет сделано за полиномиальное время, поскольку мы просто реконструируем наш график кликов и помечаем их (и удаляем их).).Для такого преобразования было бы O (V + E).

Позже вам нужно будет доказать, что ответы работают как между ответом вашей задачи, так и ответом на клику, если вы хотите доказать, что вашпроблема NP-полная.