Reducciones hacia y desde Prime.

Question

Creo que Prime (¿es el número dado un número primo?) Es un buen ejemplo de un problema de decisión.Por lo tanto, cuando estoy tratando de explicar la reducción, me gustaría dar un ejemplo de un problema relacionado con Prime.

¿Cuáles son los problemas de decisión que pueden reducirse a Prime y cómo se parecen estas reducciones?

¿Cuáles son los problemas de decisión en los que se pueden reducir los primeros y cómo se parecen estas reducciones?

Answer 1

Suponiendo que está hablando de reducciones de tiempo polinomial, ya que Prime está en $ p $ , puede reducirlo a cualquier problema de decisión no trivial (para el cual Hay al menos una instancia con la respuesta Sí y al menos una instancia con la respuesta no). Además, cualquier problema en $ P $ se puede reducir a Prime.

Para reducir una instancia $ i $ de prime a una instancia $ i_q $ de decisión no trivial problema $ q $ , deja $ y_q $ y $ n_q $ Sé un Sí y una instancia de sí y no para $ q $ , respectivamente. La reducción es la siguiente: resolver $ i $ usando una Algoritmo de tiempo polinomial para Prime. Entonces, dejemos

$$ i_q=comienzan {casos} y_q & \ mbox {si $ i $ es una instancia de sí}, \\ n_q & \ mbox {si $ i $ $ es un No hay instancia}. \ End {casos} $$

Para reducir una instancia $ i_q $ de un problema $ q \ en p $ a una instancia $ i $ de prime, resuelve $ i_q $ usando un algoritmo de tiempo polinomial para $ q $ y define

$$ i=comienzan {casos} 2 & \ mbox {if $ i_q $ es una instancia de sí}, \\ 1 & \ mbox {si $ i_q $ es un No hay instancia.} \ End {casos} $$