Если кто-то показывает, что UNIQUE k-SAT находится в P, означает ли это P = NP?

Valiant & Vazirani доказал, что SAT сводится к UNIQUE SAT при рандомизированных вероятностных сокращениях за полиномиальное время. Calabro et al . показал, что УНИКАЛЬНЫЙ k-SAT такой же жесткий, как и k-SAT. Теперь возникает вопрос: если кто-то показывает, что UNIQUE k-SAT находится в P, означает ли это P = NP?

Ссылки

1. LG Valiant и VV Vazirani: «NP так же прост, как и обнаружение уникальных решений». Теоретическая информатика 47: 85–93, 1986. ( PDF на ScienceDirect.)

2. C. Калабро, Р. Импальяццо, В. Кабанец и Р. Патури, "Сложность уникального k-SAT: лемма о выделении для k-CNF". Журнал компьютерных и системных наук 74 (3): 386–393, 2008. ( PDF в ACM Digital Library; бесплатный PDF .)

Это все еще открытый вопрос; UP, как известно, не эквивалентен NP . В статье «NP может быть не так просто, как обнаружить уникальные решения», Бейгель, Бурхман и Fortnow строят оракула, в котором P содержит UP, но P все еще не эквивалентен NP .