Reducción de NPC que no cambia una entrada

0

Tenemos el problema X e Y que sabemos que es NP-Completo. El problema X usa el gráfico G como entrada y El problema Y usa el gráfico G y la constante k como entrada.

El problema que estamos tratando de reducir, al que llamaré Z, es razonar si, dado un gráfico G y una constante k, ¿G tiene X o Y.

He estado tratando de resolver este problema y una idea que se me ocurrió es usar una entrada G y k que pueda servir como entrada para X e Y, y reducirla a G 'y k' donde G = G 'y k = k' para el problema Z

¿Es válido reducir sin cambiar una entrada?

    
pregunta SW Jeong

0 respuestas

Lea otras preguntas en las etiquetas