Problemas NP com solução única

Existe alguma classe de problemas de NP com uma solução única? Estou perguntando isso, porque quando eu estava estudando criptografia, li sobre a mochila e achei a idéia muito interessante.

complexity-theory decision-problem np cryptography Marco
fonte

Você parece estar instável com sua terminologia; Os problemas de NP podem ser arbitrariamente fáceis e geralmente são problemas de decisão (que sempre têm uma solução única, sim ou não); leia mais em nossas perguntas de referência . Eu suponho que você quer problemas difíceis de NPO com soluções exclusivas?

Raphael

Sim, eu estava querendo dizer NP completa ou NP duro, ou qualquer outra coisa que não está em P ... Desculpe e obrigado a apontar

Marco

Não sabemos se os problemas NP-completos não estão em P ...

Raphael

Respostas:

Sim, a classe é chamada UP (o U significa "inequívoco"). David ressalta nos comentários que outra resposta é americana .

UP: Se $x \in L$ , existe exatamente uma "prova" ("testemunha", "certificado", "caminho de aceitação"). E se $x \not\in L$ , existem exatamente zero "provas".

EUA: se $x \in L$ , existe exatamente uma "prova". E se $x \not\in L$ , pode haver zero provas ou mais de 2 provas, desde que não haja exatamente uma.

usul
fonte

Ou EUA, uma classe de complexidade diferente. (Para máquinas de cima, há sempre no máximo um caminho de aceitar, para US pode haver mais de um, mas eles só aceitam se há exatamente um.)