Ранжирование сложности сложных задач на практике

15

Этот вопрос тесно связан с другим постом: Фазовые переходы в NP Трудные проблемы, но он несколько иной. В то время как этот вопрос касается сложности отдельных случаев сложных проблем NP, речь идет о ранжировании сложности тех же случаев.

Существует много библиографии об эффекте, известном как фазовый переход . В частности, для случая случайных формул 3-SAT в конъюнктивной нормальной форме (CNF) известно, что существует значение R отношения предложений к переменным, так что для всех r <R формула может быть выполнена с высокой вероятностью и для r> R формула является неудовлетворительной с высокой вероятностью. Эффект фазового перехода происходит вблизи R, и он имеет замечательный эффект, заключающийся в том, что решение проблемы выполнимости для этих формул является чрезвычайно трудным на практике.

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

Можно ли ранжировать трудности трудных задач NP на практике с использованием фазового перехода 3-SAT УТС в качестве индикатора? Интуиция заключается в том, что можно ожидать, что одна проблема P1 будет сложнее, чем P2, если ее кодирование 3-SAT ближе к R (которое, как известно, близко к 4.2). Обратите внимание, что эта идея не обязательно связывает каждый конкретный экземпляр с определенной трудностью, она просто ранжирует их.

Есть несколько контраргументов, среди которых:

  1. Фазовый переход формулы 3-SAT CNF применяется к случайным формулам. Однако конкретный случай в другой проблеме имеет некоторую структуру, которая может быть использована решателями для этой проблемы - на это уже указывал Питер Шор в вышеупомянутом вопросе.
  2. Может быть так, что конкретное кодирование, используемое для преобразования конкретных экземпляров в нашей задаче в 3-SAT, играет решающую роль в соотношении предложений к переменным, приводящим к вводящим в заблуждение значениям, и, следовательно, к ошибочным классификациям - это беспокойство высказал Каве в комментарии к этому вопросу.
  3. Серж (согласно моему пониманию из его комментария к этому вопросу) поднимает вопрос о том, что можно искусственно усложнить исходную сложную задачу NP, чтобы получить формулу 3CNF, которая изменяет отношение предложений к переменным, сохраняя при этом выполнимость.

Что касается 1, все проблемы могут иметь один и тот же класс регулярности, так что могут применяться проблемы ранжирования (вместо характеристики сложности); что касается 2, существуют кодировки в конкретных задачах, которые, как известно, не являются избыточными с правилом распространения единиц, так что они должны быть предпочтительными, и, возможно, они избегают этих неправильных классификаций. Примером является Sideris et al., 2010 для случая Планирования предложений. Что касается 3, Cheeseman et al., 1991 уже рассматривал вопрос о том, сохраняют ли сопоставления между задачами эффект фазового перехода или нет, и их предварительные эксперименты, кажется, подтверждают их гипотезу, при условии, что один уменьшает исходную проблему NP и даже что « может быть далее снижается путем применения постановления к пунктам ".

Это все имеет смысл для вас? Вам известны какие-либо библиографические ссылки по этому поводу? Любое руководство будет в значительной степени признано!

Карлос Линарес Лопес
источник
Я бы предположил, что ответ будет зависеть от конкретного сокращения SAT, которое используется, хотя может быть способ обойти это.
Каве
5
Еще один контраргумент состоит в том, что к формуле 3CNF всегда можно добавить очень разреженный или очень плотный выполнимый непересекающийся компонент, изменив соотношение предложений и переменных и сохранив его выполнимость.
Серж Гасперс
@Kaveh: большое спасибо за ваши комментарии! Идея заключается в использовании не избыточных кодировок в 3-SAT, как в [Sideris et al. 2010]. Я не утверждаю, что это будет работать, но, похоже, это правильно. Я отредактировал вопрос с вашим комментарием. Еще раз спасибо!
Карлос Линарес Лопес
1
@ Серж: хорошая мысль, Серж! [Cheesemann et al., 1991] уже рассматривал вопрос о том, сохраняют ли отображения между задачами эффект фазового перехода как для задач NP, так и для задач в P (например, чтобы доказать, что они не становятся NP, когда искусственно расширены до 3-SAT, например, ) и их результаты подтверждают эти требования при условии, что они начинают с некоторых предварительных сокращений, возможно, применяя правило распространения объекта. Я отредактировал свой вопрос с вашими комментариями. Большое спасибо!
Карлос Линарес Лопес
@all: большое спасибо за внимание к моему вопросу! Это мой первый вопрос здесь (и я обязательно опубликую другие в будущем). Мне показалось впечатляющим, что менее чем за 24 часа он получил 125 посещений, 7 голосов и один человек отметил его как избранный. Спасибо вам всем!
Карлос Линарес Лопес

Ответы:

13

Хотя не исключено, что упомянутые вами технические препятствия могут быть как-то преодолены, я думаю, что в настоящее время очень мало мотивации для этого по той простой причине, что (по крайней мере, насколько мне известно) трудность NP-hard проблемы на практике, кажется, эмпирически, имеют мало общего с их близостью к фазовому переходу 3-SAT.

Сравните это с некоторыми другими способами ранжирования NP-сложных задач с точки зрения сложности: существует некоторая эмпирическая корреляция между NP-сложными задачами, которые просты на практике, и NP-сложными задачами, которые легко аппроксимировать , или которые можно трактовать с фиксированными параметрами (в смысле параметризованной сложности). В этих случаях были разработаны соответствующие понятия сокращения, которые частично объясняют эмпирические наблюдения. Однако в настоящее время, по-видимому, нет эмпирических указаний на то, что большинство сложных для NP задач, которые являются трудными на практике, являются трудными из- за их тесной связи с экземплярами 3-SAT вблизи фазового перехода. Так что не имеет особого смысла разрабатывать теорию, чтобы «объяснить» то, что на практике не представляется правдоподобным.

Тимоти Чоу
источник
2
Upvoted. Мне было бы интересно упомянуть об эмпирическом ранжировании NP-сложных проблем.
Аарон Стерлинг
Также проголосовал! Но, как и Аарон, я был бы очень заинтересован также некоторыми ссылками на рейтинг NP-сложных задач. Дайте мне пару, и я с радостью отмечу этот вопрос как ответивший! (искренне говоря, я обязательно сделаю это через пару дней, даже если вы не предоставите никаких ссылок на нагрудники) Еще раз спасибо, Тимоти!
Карлос Линарес Лопес
1
W
Тимоти!! Большое спасибо действительно !!! Это очень любезно с вашей стороны, предоставив ссылку на нагрудник !! Огромное спасибо!!
Карлос Линарес Лопес