Выборка удовлетворительная 3-SAT формулы

23

Рассмотрим следующую вычислительную задачу: мы хотим отобрать 3-SAT формулу из переменных (вариант: переменных предложений) относительно равномерного распределения вероятностей, при условии, что формула выполнима:NNм

Q1: может ли это быть эффективно достигнуто с помощью классического компьютера (со случайными битами)?

Q2: может ли это быть эффективно достигнуто квантовым компьютером?

Меня также интересуют следующие два варианта:

V2: Вы выбираете все формулы с распределением вероятностей, которое дает выполнимые формулы вдвое больше, чем неудовлетворительные формулы.

V3: вы выбираете, где вес - это число удовлетворяющих заданий (здесь мы заботимся только о Q2).

Обновление: ответ Колинса демонстрирует простой алгоритм для V3. (Я ошибался, предполагая, что это классически сложно.) Позвольте мне упомянуть еще один вариант всех трех вопросов:

Вы заранее указываете предложений, и вам нужно выбрать случайные выполнимые подмножества входных предложений.м

Гил Калай
источник
6
Очень интересный вопрос Я был бы удивлен, если есть известный алгоритм для эффективного выполнения любой из этих задач.
Джорджио Камерани

Ответы:

12

Существует простой алгоритм для V3. Я буду использовать соглашение, что существует возможных предложений, поэтому формул. (Это просто для простоты - если вы не хотите, чтобы все предложения считались действительными, это не повлияет на следующий аргумент.)(2N)328N38N3

Выберите случайное назначение из . Для каждого из возможных предложений, которые верны в этом назначении, включите предложение с вероятностью . Каждая формула появится с вероятностью, пропорциональной количеству удовлетворяющих заданий. Вариант -clause аналогичен: выберите набор размером из предложений.{0,1}N7N31/2φмм7N3

Колин Маккуиллан
источник
3
Это упомянуто во введении к Созданию выполнимых проблемных случаев , Д. Ахлиоптом, К. Гомесом, Х. Каутцем, Б. Сельманом.
Колин МакКийан,