Является ли задача NP-полной?

[Mihaylo]

Deggial: выделено отсюда

Имеется $n$-арная функция $f$. Нужно найти значения аргументов, при которых функция принимает значение логической единицы.
Отмечу, что имеется главный признак NP-полной задачи - правильность решения-сертификата проверяется за полиномиальное время. С другой стороны, на мой взгляд, данную задачу нельзя свести к известным NP-полным задачам, но можно наоборот любую NP-полную задачу свести к данной. При этом, на мой взгляд, данная задача является самой сложной, т.к. ее доступный экспоненциальный (переборный) алгоритм самый медленный и нет никаких оснований для его оптимизации. То есть это, своего рода, суперзадача. Какой же у нее статус? NP-полная?

Известно, сводимость некоторой произвольной задачи к известной NP-полной задаче автоматически относит задачу к классу NP-полных. Но не совсем ясен следующий момент: а что если наоборот NP-полная задача сводится к некоторой (наш случай)? Специально перечитывал определения, вроде как обратная сводимость ни к чему не ведет, не уверен в этом.
При этом нутро подсказывает, что поставленная задача является "прародителем" всех NP-полных задач. Самый главный вопрос - является ли поставленная задача NP-полной? Как этот вопрос решить для "прародителя", ведь он ни какой задаче не сводится?

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: не приведены попытки решения

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

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Возвращено

Если я правильно всё понял, то Вам просто нужно перечитать определение NP-задачи и определение NP-полной задачи.

Mihaylo в сообщении #1062139 писал(а):

Имеется $n$-арная функция $f$. Нужно найти значения аргументов, при которых функция принимает значение логической единицы.

Почитайте также про задачи SAT и 3-SAT.

[whitefox]

Mihaylo в сообщении #1062139 писал(а):

правильность решения-сертификата проверяется за полиномиальное время

То есть Ваша задача принадлежит классу NP, так?

Mihaylo в сообщении #1062139 писал(а):

можно . . . любую NP-полную задачу свести к данной

То есть любая задача из класса NP сводится к Вашей (видимо полиномиально сводится), так?

Если на предыдущие вопросы ответы положительны, то, пожалуйста, напомните мне определение NP-полной задачи.

[Xaositect]

NP-полнота определяется только для задач распознавания (формулировка "выполняется ли какое-то свойство", с ответом "да-нет"). Вы сформулировали свою задачу как задачу поиска ("найти объект, для которого выполняется свойство"). Класс, аналогичный NP для задач поиска, называется FNP или PC (в книге Goldreich "Computational complexity: a conceptual perspective"), для него можно определить полные задачи аналогично NP-полным.

К тому же, вы не указали, каким образом задана функция. Если функция задана формулой, то Ваша задача действительно FNP-полная. Если функция задана набором значений, то она очевидно полиномиальная.

[Mihaylo]

Deggial в сообщении #1062165 писал(а):

Почитайте также про задачи SAT и 3-SAT.

Да, это же классические задачи. Но, на мой взгляд, моя задача несколько сложнее (хотя они из одного класса сложности) и она, опять же на мой взгляд, самая сложная из данного класса. При этом под сложностью надо понимать сложность перебора.

whitefox в сообщении #1062169 писал(а):

Если на предыдущие вопросы ответы положительны, то, пожалуйста, напомните мне определение NP-полной задачи.

Еще раз прошелся по определению, почему-то оказалось, что все условия NP-полной задачи выполнены... Видимо в прошлый раз невнимательно смотрел или не в то какое-то определение.
Ну теперь глупый вопрос: по определению NP-полных задач, достаточно свести любую NPC-задачу к некоторой новой NP-задаче и тогда она автоматически попадает в класс NPC. Почему не производят проверку, что каждая новая задача из класса NPC сводится в обратную сторону хотя к одной из известных NPC-задач? А вдруг обратной сводимости нет? Если такое случится, то тогда в определении NPC-задач появится противоречие... Может я пропустил какую-то теорему об обратной сводимости?

Xaositect в сообщении #1062170 писал(а):

NP-полнота определяется только для задач распознавания (формулировка "выполняется ли какое-то свойство", с ответом "да-нет"). Вы сформулировали свою задачу как задачу поиска ("найти объект, для которого выполняется свойство"). Класс, аналогичный NP для задач поиска, называется FNP или PC (в книге Goldreich "Computational complexity: a conceptual perspective"), для него можно определить полные задачи аналогично NP-полным.

К тому же, вы не указали, каким образом задана функция. Если функция задана формулой, то Ваша задача действительно FNP-полная. Если функция задана набором значений, то она очевидно полиномиальная.

Да, Вы правы. Я как-то на автомате сформулировал не задачу распознавания свойств, а задачу поиска. Известно, что они полиномиально сводятся друг к другу. И на счет способа задания функции тоже требуется примечание.
Задача. Определить, имеются ли такие значения аргументов, при которых $n$-арная функция, заданная аналитически, принимает значение логической единицы.

[NSKuber]

Mihaylo в сообщении #1062401 писал(а):

А вдруг обратной сводимости нет? Если такое случится, то тогда в определении NPC-задач появится противоречие... Может я пропустил какую-то теорему об обратной сводимости?

Определение ещё раз прочитайте. К NP-полной задаче сводятся все (совсем все, даже те, которые мы ещё никогда не формулировали) задачи из класса NP. Именно поэтому, доказав, что NP-полная задача $A$ полиномиально сводится к задаче $B$, мы тем самым доказываем, что любая задача из NP сводится полиномиально к $B$ (сначала сведём её к $A$, пользуясь полнотой, затем к $B$). Обратная сводимость следует из определения NP-полноты!
Если вам кажется, что тут какой-то хитрый трюк и где-то вас обманывают, посмотрите самую первую NP-полную задачу, полнота которой была доказана в лоб сведением произвольной NP-задачи к данной (теорема Кука).

Mihaylo в сообщении #1062401 писал(а):

Задача. Определить, имеются ли такие значения аргументов, при которых $n$-арная функция, заданная аналитически, принимает значение логической единицы.

Вот это уже задача распознавания. Она действительно NP-полная: задача SAT сводится к ней за полиномиальное (нулевое ) время.

[Mihaylo]

NSKuber в сообщении #1062402 писал(а):

Она действительно NP-полная: задача SAT сводится к ней за полиномиальное (нулевое ) время.

Спасибо, почитаю теорему Кука.

P.S. Я рассматриваю две задачи: SAT с $n$-арной функцией и SAT с $(n-1)$-арной функцией. И вроде первая задача сводится ко второй за полиномиальное время...

[whitefox]

NSKuber в сообщении #1062402 писал(а):

Обратная сводимость следует из определения NP-полноты!

Крошечное уточнение: Если задача $B$ принадлежит классу NP, то (далее по тексту).

[Mihaylo]

NSKuber в сообщении #1062402 писал(а):

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

Теперь разобрался. Название "теорема Кука" не было озвучено, поэтому я ее не мог идентифицировать в лекции и что самое обидное, запомнить важность и назначение доказательства. А так да, в лекции доказывается полиномиальная сводимость произвольной NP-задачи к задаче ВЫП.

NSKuber в сообщении #1062402 писал(а):

Обратная сводимость следует из определения NP-полноты!

Вы называете это обратной сводимостью, я - прямой сводимостью. Но я Вас понял.

В общем итог такой: если бы теоремы Кука не было, то в определении класса NPC было бы условие сводимости в обе стороны и приходилось бы доказывать взаимную сводимость. Теорема Кука избавляет от этой сложности.

Mihaylo в сообщении #1062403 писал(а):

P.S. Я рассматриваю две задачи: SAT с $n$-арной функцией и SAT с $(n-1)$-арной функцией. И вроде первая задача сводится ко второй за полиномиальное время...

Подумал и отказался от такой мысли. SAT с $n$-арной функцией сводится к двум задачам SAT с $(n-1)$-арными функциями, к четырем задачам SAT с $(n-2)$-арными функциями и так далее. То есть сводимость не полиномиальная, а экспоненциальная... Доказательство по индукции накрылось медным тазом.

[Mihaylo]

Вопрос к аудитории: можно ли провести доказательство экспоненциальной сложности задачи следующим образом?
Определение. Задача экспоненциально сложна, если она полиномиально сводится к двум и более различным задачам того же класса эквивалентности, но меньшей размерности, при этом не сводится полиномиально к одной такой задаче.

Рассмотрим задачу выполнимости булевых формул SAT (ВЫП). Допустим булевы формулы представляют собой $t$ дизъюнкций и включают в себя $m$ булевых переменных $x_1, x_2, ..., x_m$. Рассмотрим произвольную булеву переменную $x_i$. Переменная $x_i$ может не присутствовать в $t_1$ дизъюнкциях, в $t_2$ дизъюнкциях эта переменная может присутствовать без отрицания и в $t_3$ дизъюнкциях - может присутствовать с отрицанием. При этом $t=t_1+t_2+t_3$.
Рассмотрим задачу №1 меньшей размерности $(m-1)$. При подстановке значения $x_i=1$ во все булевы формулы выполняются $t_2$ дизъюнкций, остается определить выполнимость остальных $(t_1+t_3)$ дизъюнкций. При этом заметим, в худшем случае количество дизъюнкций может оказаться тем же, что у исходной задачи (при $t_2=0$).
Задача №2 размерности $(m-1)$ получается подстановкой $x_i=0$ во все булевы формулы. В таком случае выполняются совершенно другие $t_3$ дизъюнкций, аналогичным образом остается определить выполнимость остальных $(t_1+t_2)$ дизъюнкций.
Можно свести задачи №1 и №2 к более простым подзадачам, у которых отсутствуют общие $t_1$ дизъюнкций. Очевидно, что такие задачи разные, так как имеют разные входные данные - разные $t_3$ и $t_2$ дизъюнкции. В то же время данные "простые" задачи принадлежат к тому же классу эквивалентности, что и исходная задача SAT, так как формулируются одинаково.
Задачу SAT нельзя полиномиально свести к одной из задач (№1 или №2), так как в случае определения невыполнимости одной из задач потребуется определить выполнимость другой задачи.
Можно также попытаться уменьшить размерность задачи не вдоль $m$, а вдоль $t$. Для этого необходимо избавиться от одной из дизъюнкций, предположив ее либо равной нулю, либо единице. Когда дизъюнкция равна нулю, все булевы переменные, входящие в нее, должны быть равными нулю. Когда дизъюнкция равна единице, тогда хотя бы одна из переменных должна быть равной единице. Видно, что здесь можно повторить те же рассуждения, что и в случае присвоения нуля и единицы произвольной переменной $x_i$. Подзадачи, которые будут получены в ходе этих рассуждений, будут различными и будут принадлежать к классу эквивалентности задачи SAT.

Отсюда, по определению, задача SAT экспоненциально сложна, а значит $P\ne NP$.

[NSKuber]

От того, что вы назвали новое понятие экспоненциальной сложностью, оно не входит автоматически в противоречие с определением полиномиальной разрешимости.
По крайней мере, вы этого не доказали.
Например, может случиться так, что ваша экспоненциально сложная задача размерности $m$ сводится полиномиально к двум задачам размерности $\frac{m}{2}$ (определение это допускает), а те, в свою очередь - к задачам размерности $\frac{m}{4}$ и так далее. Получаем полиномиальную сводимость к не более чем $2^{\log_2 m + 1}=2m$ одномерным тривиальным задачам, ой, экспонента потерялась

[Mihaylo]

NSKuber в сообщении #1065667 писал(а):

ой, экспонента потерялась

Это понятно. Пока мое определение и доказательство построено на интуитивном уровне, есть только некоторое направление.
Достаточно ли доказать, что исходная задача дробится на подзадачи "не столь малые" при любой стратегии разбиения? Возможно, для некоторых задач дополнительно придется доказать, что стратегия разбиения может быть удачной, но такую стратегию невозможно рассчитать за полиномиальное время.
Буду думать.

[Xaositect]

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

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

[Mihaylo]

Xaositect в сообщении #1065710 писал(а):

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

В данном случае это исключено. Потому что первая подзадача не решает некоторое количество дизъюнкций, а значит как минимум часть этих нерешенных дизъюнкций должна будет рассмотреть вторая задача. То есть исходная задача разбивается как минимум на две подзадачи одного класса сложности.

У меня достаточно наивный вопрос к специалистам: а существуют ли задачи, экспоненциальная сложность которых доказана и где можно посмотреть это доказательство?

[Mihaylo]

NSKuber в сообщении #1062402 писал(а):

Вот это уже задача распознавания. Она действительно NP-полная: задача SAT сводится к ней за полиномиальное (нулевое ) время.

Все же задача, сформулированная мною, и задача SAT - это несколько разные задачи. Задача SAT обычно формулируется с булевыми формулами, записанными в конъюнктивной форме (с такой формулировкой работал Стивен Кук). Например, задача SAT с дизъюнктивной формой булевых формул является задачей класса P. Вполне естественно, что задача SAT с произвольной формой булевых формул является NP-полной, т.к. в худшем случае придется решать задачу SAT с конъюнктивной формой и она сводится к ней...
На мой взгляд, корень решения проблемы $P=NP?$ лежит в ответе на вопрос: "Почему некоторые задачи с экспоненциальным числом вариантов решения сводятся к алгоритмам с полиномиальным числом итераций?".
Взять, например, задачу сортировки массива. Задача имеет $n!$ вариантов решения, но может быть решена за $(n\cdot \log n)$ итераций. В противопоставление полиномиальным алгоритмам сортировки можно предложить переборный алгоритм сортировки, в котором количество итераций будет надэкспоненциально (в худшем случае не менее $n!$ итераций). Каждый вариант сортировки проверяется на возрастание (или убывание) и таким образом рано или поздно будет найдено решение, которое удовлетворяет условию задачи.
Коренной вопрос: почему для задачи сортировки, решаемой переборным алгоритмом очень плохо, существуют эффективные (полиномиальные) алгоритмы? Рассмотрим одну итерацию сортировки, в которой сравниваются два элемента массива $x_i$ и $x_j$. Если алгоритм определил, что $x_i$ должен стоять левее $x_j$, то отсеивается целый ряд решений, в которых $x_i$ стоит правее $x_j$. Самое интересное, что количество отсеянных решений равно в лучшем случае $\frac{n!}{2}$, то есть довольно много и именно благодаря этому задача сортировки для своего решения не требует слишком большого количества переборов (точнее итераций).
Противоположный вопрос: Почему при решении NP-полных задач не удается одним перебором отсеивать достаточно большой ряд решений так, чтобы количество переборов стало полиномиальным? Рассмотрим задачу SAT с записью булевых формул в произвольной форме. Количество возможных решений равно $2^m$, где $m$ - это число булевых переменных. Выберем произвольно одно какое-то решение, переберем $(2^m-1)$ остальных решений. Интуитивно представляется естественным, что если $(2^m-1)$ решений не удовлетворяют условию задачи, то еще имеется шанс, что последнее (выбранное) решение удовлетворяет условию задачи; и имеется ровно такой же шанс, что последнее решение не удовлетворяет условию. Другими словами, в результате перебора $(2^m-1)$ решений отсутствует какая-либо информация о выполнимости булевых функций и обязательно потребуется осуществить последний перебор. Это неформальное рассуждение, на мой взгляд, общее направление доказательства. Считаю, что задачу SAT с произвольной формой записи булевых функций в худшем случае можно решить, только перебрав каждое из $2^m$ решений, т.к. каждое решение независимо от остальных.