Que evidência temos de ?

Seguindo a sugestão de Josh Grochow, estou convertendo meu comentário de uma pergunta anterior em uma nova.

Que evidência temos de ?$\mathsf{UP} \neq \mathsf{NP}$

Aqui é a classe de idiomas reconhecíveis pelas máquinas de Turing não determinísticas de tempo polinomial que possuem um caminho de aceitação exclusivo nas instâncias "yes" e nenhum caminho de aceitação nas instâncias "no".$\mathsf{UP}$

Obviamente , mas por que acreditamos que a contenção é rígida? A evidência que posso encontrar é a separação do oráculo : sujeita a um oráculo aleatório, . Além disso, o Zoológico de Complexidade sugere que não se acredita que \ mathsf {UP} tenha problemas completos.$\mathsf{UP} \subseteq \mathsf{NP}$U $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$$\mathsf{UP}$

Mesmo Selman e Yacobi conjeturaram que não existe um par separado modo que todos os separadores de sejam serem para . Essa conjectura implica que .( A , B ) ( A , B ) ≤ p $NP$$(A, B)$$(A, B)$$\le_T^p$U P ≠ N $NP$$UP \ne NP$

S. Even, A. Selman e J. Yacobi. A complexidade de prometer problemas com aplicativos para criptografia de chave pública. Information and Control, 61: 159-173, 1984.