Проблема: Учитывая представленный булевой схемой, генерируем равномерно случайный x ∈ { 0 , 1 } n такой, что ϕ ( x ) = 1 (или выводим ⊥, если таких нет х существует).
Очевидно, что эта проблема является NP-трудной. Мой вопрос заключается в том, является ли эта проблема также "NP-easy":
Вопрос: существует ли алгоритм, который решает вышеуказанную проблему по полиному по времени от и размеру схемы ϕ при доступе к оракулу SAT?
В качестве альтернативы, есть ли алгоритм полиномиального времени, предполагающий NP = P?
Очевидно, достаточно иметь доступ к оракулу #SAT, поэтому сложность лежит где-то между NP и #P.
Я чувствую, что это должно было быть изучено раньше, но я не могу найти ответ в Google.
Я знаю, как приблизительно решить проблему (т.е. создать удовлетворительное задание, которое является статистически близким к равномерному), используя вариант теоремы Валианта-Вазирани и / или приблизительный подсчет, но получение точно равномерного, похоже, является другой проблемой.
np-hardness
counting-complexity
reductions
Томас поддерживает Монику
источник
источник