Меня интересуют "сложные" отдельные примеры NP-полных задач.
Райан Уильямс обсудил проблему SAT0 в блоге Ричарда Липтона . SAT0 спрашивает, имеет ли экземпляр SAT конкретное решение, состоящее из всех 0. Это заставило меня задуматься о создании экземпляров SAT, которые, вероятно, будут «сложными».
Рассмотрим экземпляр SAT с предложениями и переменными, где является «достаточно большим» в том смысле, что он попадает в область за пределами фазового перехода, где почти все экземпляры являются неудовлетворительными. Пусть будет случайным назначением значений .m n α = m / n x ϕ
Можно ли изменить для получения нового экземпляра , чтобы был "в значительной степени похож" на , но чтобы было удовлетворительным условием для ?ϕ | x ϕ | x ϕ x ϕ | Икс
Например, можно попытаться добавить к каждому предложению случайно выбранный литерал из решения, чего еще нет в предложении. Это гарантирует, что является решением.
Или это безнадежно, что приводит к быстрому алгоритму поиска «скрытого» решения, как в следующей недавней статье?
- Уриэль Фейдж и Дорит Рон, Поиск скрытых кликов за линейное время , DMTCS proc. AM, 2010, 189–204.
Я знаю о дискуссии Кука и Митчелла и работе, на которую они ссылаются. Тем не менее, я не смог найти ничего о том, что происходит со структурой формулы, когда кто-то пытается явно вставить в нее удовлетворительное назначение. Если это фольклор, указатели будут очень кстати!
- Стивен А. Кук и Дэвид Дж. Митчелл, Нахождение трудных примеров проблемы удовлетворенности: обзор , серия DIMACS по дискретной математике и теоретической информатике 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. ( PS )
источник
Если я правильно понимаю саму суть вашего вопроса, вы хотите взять сравнительно легкий экземпляр (так как вы ставите себя в районе , где ), и преобразовать его в сложное путем вложения решения. Я сомневаюсь, что это сработает.мN> 4.3
Экспериментальные данные показывают, что при построении случайного экземпляра «вокруг» заранее определенного решения такой случай будет легче обычного (по сравнению с аналогичными экземплярами, имеющими одинаковые n и m ). Это как если бы скрытое решение помогло решить SAT, направляя его через пространство поиска. Обычно, чтобы построить такой экземпляр, мы генерируем случайные предложения как обычно (например, выбирая k литералов случайным образом и отрицая каждый из них с вероятностью p = 1Икс N м К ) но мы отбрасываем те пункты, которые не удовлетворены нашим скрытым решениемx. Что касается вашего подхода построенияϕ| xот и жесткий случайϕ: я никогда не пробовал это, но я «чувствую», чтоϕ| хстанет легче, если не тривиально. Я полагаю, что выполнение этого увеличило бы количество обращенийлитераловx(количество обращений литералаl- это число вхожденийlв заданной формуле), и что это привело бы решатель SAT к цели. Может быть, пространства решенийϕиϕ| Икср = 12 Икс ϕ | Икс φ ϕ | Икс Икс L L φ ϕ | Икс будет аналогичным (если не почти идентичным), как это происходит в примере SAT0 Райана Уильямса (почти идентичные пространства решений, но совершенно другой твердости). Вы пробовали свой подход на практике? Было бы интересно посмотреть, как один и тот же SAT-решатель ведет себя на и на ϕ | х .φ ϕ | Икс
РЕДАКТИРОВАТЬ 1 (23 сентября 2010 г.): Подумав немного больше, я чувствую, что на самом деле пространство решения будет сильно отличаться от ϕ . Вы добавляете литерал в каждое предложение, так что вы даете большую степень свободы таким предложениям (т. Е. У каждого предложения больше шансов быть удовлетворенным): возможно, результирующее пространство решений будет массово преобразовано.ϕ | Икс φ
РЕДАКТИРОВАТЬ 2 (1 октября 2010): я думал о следующей очень простой и не оригинальной идее. Дан начальный экземпляр и присваивание x :φ Икс
Удалить из все те пункты, которые не удовлетворены x . Это увеличит пространство решения, и в него должно быть вставлено x .φ Икс Икс
Предположим, вы удалили статей. Теперь случайным образом добавьте m x новых предложений, следя за тем, чтобы они не были неудовлетворены x (это снова сузит пространство решения, но без выталкивания x из него).мИкс мИкс Икс Икс
Я не знаю, сработает ли это или нет. Я еще не пробовал. Точнее, я не уверен, что шагу 1 всегда удается внедрить в пространство решения (возможно, x исключается некоторой комбинацией предложений, даже если каждое из них не неудовлетворено x ?).Икс Икс Икс
источник
Наилучший способ генерирования сложных экземпляров проблем с NP-завершением, о которых я знаю, - это использовать отображение Кука, чтобы свести тщательно отобранные экземпляры некоторых других сложных задач NP (таких как проблема дискретного логарифма или целочисленная факторизация) к SAT. Это те же «сложные проблемы», которые используются математиками для обеспечения криптографической безопасности в таких протоколах, как RSA и Diffie-Hellman.
источник