За решение этой задачки Марк Цукерберг учредил премию в размере 3.000.000 $ Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти?
За решение этой задачки Марк Цукерберг учредил премию в размере 3.000.000 $ Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Данная проблема описывает класс задач, известный как NP (недетерминированно полиномиальное время), в котором проверка возможного решения занимает полиномиальное время, но сам поиск решения может быть более сложным. NP-полнота означает, что задача является "трудной" в том смысле, что для ее решения не известен алгоритм, работающий за полиномиальное время.
Исходя из вышесказанного, ответ на вопрос сводится к тому, что наличие сертификата не обязательно означает, что само решение можно быстро найти. NP-полные задачи также входят в класс NP, но их сложность не меньше, чем у других NP-полных задач. Таким образом, наличие сертификата для проверки решения не гарантирует простоту поиска самого решения.