Jakie mamy dowody na ?

Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie.

Jakie mamy dowody na ?$\mathsf{UP} \neq \mathsf{NP}$

Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną ścieżkę akceptacji w instancjach „tak” i brak ścieżki akceptacji w instancjach „nie”.$\mathsf{UP}$

Oczywiście , ale dlaczego mielibyśmy sądzić, że przechowywanie jest surowe? Dowodem, który mogę znaleźć, jest separacja wyroczni : podlega losowej wyroczni, . Zoo złożoności sugeruje również, że nie uważa się , że ma pełne problemy.$\mathsf{UP} \subseteq \mathsf{NP}$$\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$$\mathsf{UP}$

Nawet Selman i Yacobi Przypuszcza się, że nie istnieje odłączony -pair ( , B ) tak, że wszystkie separatory ( A , B ) są ≤ P T -hard o N P . Hipoteza ta sugeruje, że u P ≠ N P .$NP$$(A, B)$$(A, B)$$\le_T^p$$NP$$UP \ne NP$

S. Even, A. Selman i J. Yacobi. Złożoność obiecujących problemów z aplikacjami do kryptografii z kluczem publicznym. Information and Control, 61: 159–173, 1984.