Jeśli ktoś pokazuje, że UNIKALNY k-SAT jest w P, to czy oznacza to, że P = NP?

Valiant i Vazirani udowodnili, że SAT można zredukować do UNIKALNEGO SAT przy randomizowanych probabilistycznych redukcjach czasu wielomianowego. Calabro i in . pokazał, że UNIKALNY k-SAT jest tak trudny jak k-SAT. Teraz pytanie brzmi: jeśli ktoś pokaże, że UNIKALNY k-SAT jest w P, czy oznacza to, że P = NP?

Bibliografia

1. LG Valiant i VV Vazirani, „NP jest tak łatwe, jak wykrywanie unikalnych rozwiązań”. Theoretical Computer Science 47: 85–93, 1986. ( PDF w ScienceDirect.)

2. C. Calabro, R. Impagliazzo, V. Kabanets i R. Paturi, „Złożoność unikalnego k-SAT: lemat izolacji dla k-CNF”. Journal of Computer and System Sciences 74 (3): 386–393, 2008. ( PDF w ACM Digital Library; bezpłatny PDF .)

To wciąż otwarte pytanie; UP nie jest znane jako równoważne NP . W artykule „NP może nie być tak łatwe jak wykrywanie unikalnych rozwiązań” Beigel, Burhman i Fortnow konstruują wyrocznię, pod którą P zawiera UP, ale P wciąż nie jest równoważne NP .