Problemas NP con solución única

¿Hay alguna clase de problemas NP que tengan una solución única? Lo pregunto porque cuando estaba estudiando criptografía leí sobre la mochila y la idea me pareció muy interesante.

complexity-theory decision-problem np cryptography Marco
fuente

Pareces ser inestable en tu terminología; Los problemas de NP pueden ser arbitrariamente fáciles, y generalmente son problemas de decisión (que siempre tienen una solución única, sí o no); Lea más en nuestras preguntas de referencia . ¿Asumo que quieres problemas difíciles de NPO con soluciones únicas?

Raphael

Sí, me refería a NP completo o NP difícil, o lo que sea que no esté en P ... Lo siento y gracias por señalar

Marco

No sabemos si los problemas de NP completo no están en P ...

Raphael

Respuestas:

Sí, la clase se llama UP (la U significa "inequívoco"). David señala en los comentarios que otra respuesta es EE . UU .

ARRIBA: si $x \in L$ , entonces hay exactamente una "prueba" ("testigo", "certificado", "ruta de aceptación"). Si $x \not\in L$ , hay exactamente cero "pruebas".

EE. UU .: si $x \in L$ , entonces hay exactamente una "prueba". Si $x \not\in L$ , puede haber cero pruebas o más de 2 pruebas, siempre que no haya exactamente una.

usul
fuente

O EE. UU., Una clase de complejidad diferente. (Para las máquinas UP, siempre hay a lo sumo un camino de aceptación, para los EE. UU. Puede haber más de uno, pero solo aceptan si hay exactamente uno)