Этот вопрос тесно связан с другим постом: Фазовые переходы в NP Трудные проблемы, но он несколько иной. В то время как этот вопрос касается сложности отдельных случаев сложных проблем NP, речь идет о ранжировании сложности тех же случаев.
Существует много библиографии об эффекте, известном как фазовый переход . В частности, для случая случайных формул 3-SAT в конъюнктивной нормальной форме (CNF) известно, что существует значение R отношения предложений к переменным, так что для всех r <R формула может быть выполнена с высокой вероятностью и для r> R формула является неудовлетворительной с высокой вероятностью. Эффект фазового перехода происходит вблизи R, и он имеет замечательный эффект, заключающийся в том, что решение проблемы выполнимости для этих формул является чрезвычайно трудным на практике.
Так как для доказательства NP-твердости данной проблемы необходимо показать, что существует сокращение Тьюринга за полиномиальное время для NP-полной задачи и что NP-полные задачи могут быть преобразованы среди них за полиномиальное время, тогда естественно возникает следующий вопрос:
Можно ли ранжировать трудности трудных задач NP на практике с использованием фазового перехода 3-SAT УТС в качестве индикатора? Интуиция заключается в том, что можно ожидать, что одна проблема P1 будет сложнее, чем P2, если ее кодирование 3-SAT ближе к R (которое, как известно, близко к 4.2). Обратите внимание, что эта идея не обязательно связывает каждый конкретный экземпляр с определенной трудностью, она просто ранжирует их.
Есть несколько контраргументов, среди которых:
- Фазовый переход формулы 3-SAT CNF применяется к случайным формулам. Однако конкретный случай в другой проблеме имеет некоторую структуру, которая может быть использована решателями для этой проблемы - на это уже указывал Питер Шор в вышеупомянутом вопросе.
- Может быть так, что конкретное кодирование, используемое для преобразования конкретных экземпляров в нашей задаче в 3-SAT, играет решающую роль в соотношении предложений к переменным, приводящим к вводящим в заблуждение значениям, и, следовательно, к ошибочным классификациям - это беспокойство высказал Каве в комментарии к этому вопросу.
- Серж (согласно моему пониманию из его комментария к этому вопросу) поднимает вопрос о том, что можно искусственно усложнить исходную сложную задачу NP, чтобы получить формулу 3CNF, которая изменяет отношение предложений к переменным, сохраняя при этом выполнимость.
Что касается 1, все проблемы могут иметь один и тот же класс регулярности, так что могут применяться проблемы ранжирования (вместо характеристики сложности); что касается 2, существуют кодировки в конкретных задачах, которые, как известно, не являются избыточными с правилом распространения единиц, так что они должны быть предпочтительными, и, возможно, они избегают этих неправильных классификаций. Примером является Sideris et al., 2010 для случая Планирования предложений. Что касается 3, Cheeseman et al., 1991 уже рассматривал вопрос о том, сохраняют ли сопоставления между задачами эффект фазового перехода или нет, и их предварительные эксперименты, кажется, подтверждают их гипотезу, при условии, что один уменьшает исходную проблему NP и даже что « может быть далее снижается путем применения постановления к пунктам ".
Это все имеет смысл для вас? Вам известны какие-либо библиографические ссылки по этому поводу? Любое руководство будет в значительной степени признано!
источник
Ответы:
Хотя не исключено, что упомянутые вами технические препятствия могут быть как-то преодолены, я думаю, что в настоящее время очень мало мотивации для этого по той простой причине, что (по крайней мере, насколько мне известно) трудность NP-hard проблемы на практике, кажется, эмпирически, имеют мало общего с их близостью к фазовому переходу 3-SAT.
Сравните это с некоторыми другими способами ранжирования NP-сложных задач с точки зрения сложности: существует некоторая эмпирическая корреляция между NP-сложными задачами, которые просты на практике, и NP-сложными задачами, которые легко аппроксимировать , или которые можно трактовать с фиксированными параметрами (в смысле параметризованной сложности). В этих случаях были разработаны соответствующие понятия сокращения, которые частично объясняют эмпирические наблюдения. Однако в настоящее время, по-видимому, нет эмпирических указаний на то, что большинство сложных для NP задач, которые являются трудными на практике, являются трудными из- за их тесной связи с экземплярами 3-SAT вблизи фазового перехода. Так что не имеет особого смысла разрабатывать теорию, чтобы «объяснить» то, что на практике не представляется правдоподобным.
источник