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

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

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

можно увидеть в , -hard и -hard. Что-нибудь более известно о его сложности?$\Delta_2$$\mathsf{UP}$$\mathsf{coNP}$

Ваша проблема известна как проблема которая является -complete. Проблема в но неизвестно, является ли она -твердой при детерминированных полиномиальных сокращениях времени, где класс .$\text{UNIQUE-SAT}$$\mathsf{US}$$\mathsf{D^p}$$\mathsf{D^p}$$\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$

Как было показано Пападимитриу и Яннакис [1] , что множество однозначно выполнимых формул содержится в . Это следует из определения : пусть быть САТ, и пусть множество формул с или более удовлетворяющих назначений. Что касается -hardness из , Blass и Гуревич [2] дал частичный ответ. С одной стороны , они показали , не релятивизации техники доказательства необходимо будет решить вопрос. Тем не менее, доблестный и Вазирани [3] дал рандомизированное полином сокращение времени от , показывающий -hardness из$\mathsf{D^p}$$\mathsf{D^p}$$L_1$$L_2$$2$$\mathsf{D^p}$$\text{UNIQUE-SAT}$$\text{SAT}$$\mathsf{D^p}$$\text{UNIQUE-SAT}$ при рандомизированных полиномиальных сокращениях времени.

Когда известно, что проблема имеет не более одного назначения или нет назначений, проблема обещания называется . Теорема Валианта – Вазирани гласит, что если для существует алгоритм полиномиального времени , то . Чтобы доказать свою теорему, они показали, что задача обещания является -твердой при рандомизированных полиномиальных сокращениях времени. Следствие, вытекающее из теоремы Валианта – Вазирани, состоит в том, что является полным для при рандомизированных полиномиальных сокращениях времени.$\text{UNAMBIGUOUS-SAT}$$\text{UNAMBIGUOUS-SAT}$$\mathsf{NP}=\mathsf{RP}$$\text{UNAMBIGUOUS-SAT}$$\mathsf{NP}$$\text{UNIQUE-SAT}$$\mathsf{D^p}$

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

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

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