Является ли обязательным, чтобы "сокращение probl bee inm было сделано за полиномиальное время", чтобы оно было завершено NP?
Для того чтобы задача была NP-полной, она должна принадлежать классу NP, и должен быть алгоритм за полиномиальное время, чтобы свести ее к NP-полной задаче.
А что если у нас есть только экспоненциальный алгоритм уменьшения времени? Будет ли эта проблема называться NP-полной? Или таких проблем нет?
РЕДАКТИРОВАТЬ: Также, пожалуйста, скажите мне, есть ли такая проблема, и если она существует, то к какому классу она относится?
4 ответа
Are such problems NP-complete?
Нет доказательств:
Пусть ваша проблема = A.
Пусть NP-полная задача сводится к (по крайней мере) экспоненциальному времени = B. "По крайней мере", потому что вы можете выполнить дополнительную тривиальную работу, чтобы перейти к экспоненциальному времени, или следовать менее оптимальному подходу (чтобы доказать, что не существует более эффективной стратегии сокращения, вероятно, довольно трудной, вероятно, в том же парке, что и N!= NP, которая, на сегодняшний день, не была решена).
Поскольку B NP-полна, "каждая задача из NP сводится к B за полиномиальное время".
Если A находится в NP, то оно должно быть сведено за полиномиальное время к B. Но это не так, поэтому его нет в NP.
Таким образом, он не может быть NP-завершенным.
Проще говоря - любая проблема в NP должна быть не более сложной, чем A, и это явно не так.
Are there such problems?
Я думаю, что это может быть такая проблема: (рекурсивный рюкзак) (я не возражаю против одного или двух комментариев относительно того, является ли это кем-то умным)
По заданному набору предметов, каждый из которых имеет вес и значение, найти подмножество с максимальным общим весом A, а также найти подмножество в этом подмножестве с некоторым максимальным общим весом C с целью максимизировать сумму значений двух. подмножества.
To which class does it belong?
Я почти уверен, что специально для них нет названия, но я думаю, что многие (или все?) Из них NP-hard. Доказательство: (по крайней мере, для вышеуказанной проблемы, если предположить, что это такая проблема)
Давайте предположим, что приведенный выше пример является такой проблемой, и пусть он = H. Итак, предположим, что у нас есть оракул, который может решить вышеизложенное в постоянное время. Но проблема рюкзака является просто частным случаем вышеупомянутого (C = 0), поэтому мы можем решить проблему рюкзака за постоянное время (то есть за полиномиальное время) с помощью оракула.
Не уверен в том, чтобы доказать это в общем. Но любая конкретная проблема может быть решена путем сведения данной проблемы к вышеупомянутой проблеме или путем уменьшения проблемы, с которой данная проблема сводится к проблеме ранца.
РЕДАКТИРОВАТЬ: О, похоже, у них действительно может быть имя, 2 EXPTIME.
Он может считаться NP-завершенным только в том случае, если другие задачи NP могут быть сведены к нему за полиномиальное время. Причина, по которой это полезное определение, состоит в том, что если мы найдем алгоритм полиномиального времени для одного, он автоматически даст один для всех задач NP. Если бы мы допустили экспоненциальное сокращение времени, но нашли решение уменьшенной задачи за полиномиальное время, это на самом деле не помогло бы нам решить ту, к которой мы ее сократили.
Надеюсь это поможет.
Полнота в теории сложности всегда определяется для определенного вида сокращений, иногда известных из контекста и, таким образом, явно не упомянутых. Известный класс NP-полных задач определен как полный для полиномиальных сокращений времени по причинам, приведенным в ответе Ричарда Раста.
Вы можете определить класс NP-полных задач для сокращений EXPTIME, но этот класс не очень интересен. Если сокращение допускается экспоненциальным временем, то оно может полностью решить исходную проблему и создать тривиальный экземпляр целевой задачи. Это означает, что каждая проблема в NP сводится к любой другой проблеме посредством такого типа сокращений, поэтому каждая проблема в NP является NP-полной для экспоненциальных сокращений времени.
Короткая версия: сокращения интересны только в том случае, если они (по крайней мере, предположительно) слабее, чем класс задач, которые сокращаются.
Как было отмечено ранее, направление вашего вопроса неверно. Задача A является NP-полной по определению, если каждая проблема B в NP может быть сведена за полиномиальное время к проблеме A. Поэтому я предполагаю, что ваш вопрос заключается в том, должно ли это сокращение быть за полиномиальное, а не экспоненциальное время.
Если вы допустили экспоненциальное сокращение времени: примите следующее решение задачи X: "Является ли вход ДА?" Это почти самое простое решение проблемы. Ответ ДА, если ввод ДА, ответ НЕТ, если ввод ДА. Но каждая проблема в NP может быть сведена к проблеме X в экспоненциальном времени. Конечно, мы не хотим называть проблему X "NP-полной". Следовательно, экспоненциальное сокращение времени недопустимо, поскольку его использование делает термин "NP-полный" совершенно бессмысленным.