Выборка равномерно случайного удовлетворяющего задания

14
Проблема: Учитывая представленный булевой схемой, генерируем равномерно случайный x { 0 , 1 } n такой, что ϕ ( x ) = 1 (или выводим ⊥, если таких нет х существует). φ:{0,1}N{0,1}Икс{0,1}Nφ(Икс)знак равно1Икс

Очевидно, что эта проблема является NP-трудной. Мой вопрос заключается в том, является ли эта проблема также "NP-easy":

Вопрос: существует ли алгоритм, который решает вышеуказанную проблему по полиному по времени от и размеру схемы ϕ при доступе к оракулу SAT? Nφ

В качестве альтернативы, есть ли алгоритм полиномиального времени, предполагающий NP = P?

Очевидно, достаточно иметь доступ к оракулу #SAT, поэтому сложность лежит где-то между NP и #P.


Я чувствую, что это должно было быть изучено раньше, но я не могу найти ответ в Google.

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

Томас поддерживает Монику
источник

Ответы:

19

Да.

(резервные ссылки на случай, если один из них выйдет из строя: 1 2 3 4 )

Резервная ссылка, на случай, если все эти ссылки прекратятся: Белларе, Михир, Одед Голдрайх и Эрез Петранк. «Равномерное поколение NP-свидетелей с использованием NP-оракула». Информация и вычисления 163,2 (2000): 510-526.

Лоренцо Найт
источник