Intuición para la clase UP

La clase UP se define como tal:

La clase de problemas de decisión que una máquina NP puede resolver

Si la respuesta es 'sí', se acepta exactamente una ruta de cálculo.

Si la respuesta es 'no', todas las rutas de cálculo se rechazan.

Estoy tratando de desarrollar la intuición para esta definición.

¿Se puede decir que los problemas UP son problemas con soluciones únicas (por ejemplo, factorización prima)?

Eso me parece cercano a la verdad; pero no puedo evitar pensar que eso significaría, ya que UP contiene P y está contenido en NP, en caso de P = NPque lo obtengamos P = UP = NP, entonces todos los problemas también NPtienen soluciones únicas, lo que parece algo que probablemente no sea cierto: P != NPpor reducción al absurdo. Espero que no haya demasiadas conjeturas y dudas en este párrafo para su gusto.

cc.complexity-theory complexity-classes valya
fuente

La definición de "solución única" es problemática: resolver juegos de paridad , por ejemplo, está en UP (UP

coUP, de hecho), pero puede haber muchas estrategias ganadoras. El testigo único está más involucrado.

\cap

$\cap$

Shaull

hm, entonces eso significaría que hay un algoritmo para una máquina de Turing no determinista, que no es "probar todas las soluciones de manera no determinista" (pensé que esa es la idea en el corazón de la equivalencia de definiciones de NP para n.-d. y d. Tm), pero algo más sofisticado, que siempre conduce al resultado único de muchos posibles ... ¿Es eso cierto? ¿Hay otra forma de expresarlo, por ejemplo, usando solo la idea de una Tm determinista (uno puede definir NP usando solo eso)?

valya

La intuición de un testigo único es correcta, pero debe usarse con cuidado, ya que no significa que cada NTM tenga una carrera única.

Shaull

¡Me encanta esta pregunta! Tuve exactamente la misma confusión, pero no vi la manera inteligente de traducir esta confusión en una simple prueba de que P! = NP. ¡Bien hecho!

Vincent

Por cierto, su pregunta de su último comentario ha sido respondida en la página de Wikipedia para la clase UP

Vincent

Respuestas:

$\mathsf{NP}$ Otro tipo de solución que funciona igualmente bien es la asignación de una orientación a cada borde (creando rutas dirigidas de como máximo el número requerido de vértices). Estos dos tipos de soluciones se pueden verificar en tiempo polinómico, pero mediante diferentes algoritmos, y también tienen diferentes propiedades combinatorias. Por ejemplo, para una instancia de problema típica, el número de asignaciones de color de vértice será diferente del número de orientaciones de borde. Una gran cantidad de investigación sobre la aceleración de algoritmos exponenciales para problemas de tipo NP puede interpretarse como la búsqueda de una nueva familia de soluciones para el mismo problema que tiene menos posibilidades de verificar.

$\mathsf{P}$ $\mathsf{NP}$ $\mathsf{UP}$ $\mathsf{P}\subset\mathsf{UP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}=\mathsf{UP}$ . Por lo tanto, no hay contradicción entre el hecho de que la solución de cadena vacía es única y el hecho de que algún otro tipo de solución para el mismo problema no es único.

David Eppstein
fuente

U P = N P

$UP=NP$

[a, b]

$[a,b]$

a, b \sim N^{\frac{1}{4}}

$a,b\sim N^{\frac{1}{4}}$

a < b

$a<b$

Nuevamente, está asumiendo incorrectamente que la solución solo puede ser el factor que está buscando. Puede haber otras formas de resolver el mismo problema (es decir, obtener una respuesta de sí o no para el N dado) que no consisten en un factor. Y si P = NP, la cadena vacía cumple con los requisitos técnicos de una solución NP (puede verificarla en tiempo polinómico) y, de hecho, no es un factor, sino una solución al mismo problema.

David Eppstein el

¡Esta respuesta es absolutamente brillante ya que nos enseña aún más de lo que se pide!

Vincent

$\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{NPMV}$ $\mathsf{NP}$

$\mathsf{NPSV}$ $\mathsf{NPMV}$

$\mathsf{NP}$ $\mathsf{NPMV}$ $\mathsf{NPSV}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{UP}$ $\mathsf{NP} = \mathsf{UP}$ $L \in \mathsf{NP}$ $\mathsf{UP}$ $L$ $\mathsf{NP}$ $L$

Joshua Grochow
fuente