Сложность принятия решения, если формула имеет ровно 1 удовлетворяющее назначение

11

Решение проблемы

Учитывая булеву формулу , имеет ли ровно одно удовлетворяющее присваивание?ϕϕ

можно увидеть в , -hard и -hard. Что-нибудь более известно о его сложности?Δ2UPcoNP

sdcvvc
источник

Ответы:

11

Ваша проблема известна как проблема которая является -complete. Проблема в но неизвестно, является ли она -твердой при детерминированных полиномиальных сокращениях времени, где класс .UNIQUE-SATUSDpDpDp={L1L2¯L1,L2NP}

Как было показано Пападимитриу и Яннакис [1] , что множество однозначно выполнимых формул содержится в . Это следует из определения : пусть быть САТ, и пусть множество формул с или более удовлетворяющих назначений. Что касается -hardness из , Blass и Гуревич [2] дал частичный ответ. С одной стороны , они показали , не релятивизации техники доказательства необходимо будет решить вопрос. Тем не менее, доблестный и Вазирани [3] дал рандомизированное полином сокращение времени от , показывающий -hardness изDpDpL1L22DpUNIQUE-SATSATDpUNIQUE-SAT при рандомизированных полиномиальных сокращениях времени.

Когда известно, что проблема имеет не более одного назначения или нет назначений, проблема обещания называется . Теорема Валианта – Вазирани гласит, что если для существует алгоритм полиномиального времени , то . Чтобы доказать свою теорему, они показали, что задача обещания является -твердой при рандомизированных полиномиальных сокращениях времени. Следствие, вытекающее из теоремы Валианта – Вазирани, состоит в том, что является полным для при рандомизированных полиномиальных сокращениях времени.UNAMBIGUOUS-SATUNAMBIGUOUS-SATNP=RPUNAMBIGUOUS-SATNPUNIQUE-SATDp


[1] Пападимитриу, Христос Х. и Михалис Яннакакис. «Сложность граней (и некоторые аспекты сложности).» Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений. ACM, 1982.

[2] Blass, Андреас, и Юрий Гуревич. «Об уникальной проблеме выполнимости». Информация и контроль 55.1 (1982): 80-88.

[3] Валиант, Лесли Дж. И Виджей В. Вазирани. «NP так же прост, как и обнаружение уникальных решений». Теоретическая информатика 47 (1986): 85-93.

Юхо
источник
Спасибо за ответ; Я также нашел в книге главу о том, что существование детерминированной редукции открыто.
sdcvvc