Рад, что Вы разобрались.
Но то, что эта задача не из P и не из NP понятно, т.к. в этих классах лежат только задачи разрешимости (т.е. задачи на да/нет).
Пример для клики не заметил. Если Вы хотите организовать самую большую вечеринку для «своих» (то есть, чтобы на вечеринке каждый знал каждого), то Вам необходимо решить задачу о максимальной клике. Обозначьте друзей вершинами, проведите ребро между двумя вершинами, если два этих друга знакомы и решите задачу о максимальной клике.
Да, это синонимы.
Эта задача как раз не из NP. Классу NP принадлежат задачи разрешимости. Это задача оптимизации.
Кроме того NP-трудная отличается от NP тем, что она не легче любой задачи из NP. То есть, она трудная задача. Например, проверить, является ли одно число на 1 больше другого — это тоже задача из NP. Но она не NP-трудная.
Возможно, это связано с тем, что на контестах обычно требуются точные детерминированные решения. А для NP-трудных задач на данный момент известны только экспоненциальные по времени решения, что не нравится контестам. Применений у NP-трудных задач действительно много. Поэтому люди и ищут все более и более быстрые и изощрённые способы решения NP-трудных задач.
Например, Вы хотите расставить как можно меньше вышек мобильной связи, но хотите покрыть какой-то набор дорог. Это и есть задача о вершинном покрытии.
Если Вы хотите рассадить в своем зоопарке по клеткам бегемотов, то Вам необходимо решить задачу о независимом множестве. Ведь известно, что бегемот из первой клетки не даст спокойно жить бегемотам из нулевой и третьей клеток (т.к. в графе есть ребра 1-0 и 1-3) и.т.д. Так, Вам нужно выбрать максимальное количество клеток, попарно не соединенных ребрами. Это и есть задача о независимом множестве.
alexeygrigorev: Да, конечно расскажу.
mrShadow: Немного уточню.
NP-hard (NP-трудная, NP-сложная) задача — это задача, мгновенно получая ответы на которую, мы смогли бы за полиномиальное время решить любую задачу из класса NP.
Или, что тоже самое, смогли бы решить какую-нибудь NP-полную задачу.
Неформально это значит, что NP-трудная задача не проще, чем все задачи из класса NP. Например, если бы NP-трудная задача решилась за полиномиальное время, то получилось бы, что какая-то NP-полная задача тоже решается за полиномиальное время, то есть P=NP.
NP-complete (NP-полная) задача — это NP-трудная задача, которая сама к тому же принадлежит классу NP.
В классе NP лежат задачи разрешимости (decision problem). Это задачи, на которые есть ответ да/нет. Например, к NP (и NP-полным) задачам относится следующая версия задачи о вершинном покрытии: «Существует ли в графе вершинное покрытие мощности не более k?». Это вопрос на да/нет.
Также бывают задачи оптимизации (NP optimization problem). Это NP-задачи, в которых требуется найти лучшее решение. Это уже не задачи на да/нет. Следовательно, они не лежат в классе NP. Но многие из них являются NP-трудными. Например, NP-трудной является задача из топика: «Найти минимальное вершинное покрытие».
Умея решать NP-сложную задачу (например, задачу из топика) можно быстро решить NP-полную задачу (например, задачу о существовании в графе покрытия <=k). Действительно, пусть мы нашли минимальное вершинное покрытие. Его размер m. Если m<=k, то в графе существует вершинное покрытие мощности <=k, иначе — не существует.
Но то, что эта задача не из P и не из NP понятно, т.к. в этих классах лежат только задачи разрешимости (т.е. задачи на да/нет).
Эта задача как раз не из NP. Классу NP принадлежат задачи разрешимости. Это задача оптимизации.
Кроме того NP-трудная отличается от NP тем, что она не легче любой задачи из NP. То есть, она трудная задача. Например, проверить, является ли одно число на 1 больше другого — это тоже задача из NP. Но она не NP-трудная.
Например, Вы хотите расставить как можно меньше вышек мобильной связи, но хотите покрыть какой-то набор дорог. Это и есть задача о вершинном покрытии.
Если Вы хотите рассадить в своем зоопарке по клеткам бегемотов, то Вам необходимо решить задачу о независимом множестве. Ведь известно, что бегемот из первой клетки не даст спокойно жить бегемотам из нулевой и третьей клеток (т.к. в графе есть ребра 1-0 и 1-3) и.т.д. Так, Вам нужно выбрать максимальное количество клеток, попарно не соединенных ребрами. Это и есть задача о независимом множестве.
mrShadow: Немного уточню.
NP-hard (NP-трудная, NP-сложная) задача — это задача, мгновенно получая ответы на которую, мы смогли бы за полиномиальное время решить любую задачу из класса NP.
Или, что тоже самое, смогли бы решить какую-нибудь NP-полную задачу.
Неформально это значит, что NP-трудная задача не проще, чем все задачи из класса NP. Например, если бы NP-трудная задача решилась за полиномиальное время, то получилось бы, что какая-то NP-полная задача тоже решается за полиномиальное время, то есть P=NP.
NP-complete (NP-полная) задача — это NP-трудная задача, которая сама к тому же принадлежит классу NP.
В классе NP лежат задачи разрешимости (decision problem). Это задачи, на которые есть ответ да/нет. Например, к NP (и NP-полным) задачам относится следующая версия задачи о вершинном покрытии: «Существует ли в графе вершинное покрытие мощности не более k?». Это вопрос на да/нет.
Также бывают задачи оптимизации (NP optimization problem). Это NP-задачи, в которых требуется найти лучшее решение. Это уже не задачи на да/нет. Следовательно, они не лежат в классе NP. Но многие из них являются NP-трудными. Например, NP-трудной является задача из топика: «Найти минимальное вершинное покрытие».
Умея решать NP-сложную задачу (например, задачу из топика) можно быстро решить NP-полную задачу (например, задачу о существовании в графе покрытия <=k). Действительно, пусть мы нашли минимальное вершинное покрытие. Его размер m. Если m<=k, то в графе существует вершинное покрытие мощности <=k, иначе — не существует.