Reduções de e para prime

Question

Eu acho que Prime (é o número dado que um número primo?) é um bom exemplo de um problema de decisão.Portanto, quando estou tentando explicar a redução, gostaria de dar um exemplo de um problema relacionado ao Prime.

Quais são os problemas de decisão que podem ser reduzidos a primo e como essas reduções se parecem?

Quais são os problemas de decisão que a Prime pode reduzir e como essas reduções se parecem?

Answer 1

Supondo que você esteja falando sobre reduções de tempo polinômio, já que a Prime está em $ P $ , você pode reduzi-lo a qualquer problema de decisão não trivial (para o qual Há pelo menos uma instância com resposta sim e pelo menos uma instância com resposta não). Além disso, qualquer problema na $ P $ pode ser reduzido a primo.

Para reduzir uma instância $ i $ de primo para uma instância $ i_Q $ de decisão não trivial problema $ q $ , deixe $ y_q $ e $ n_q $ seja um sim e uma instância para $ q $ , respectivamente. A redução é a seguinte: resolver $ i $ usando um Algoritmo de tempo polinômio para o Prime. Então, deixe

$$ I_Q=begin {casos} y_q & \ mbox {se $ i $ é uma instância sim}, \\ n_q & \ mbox {se $ i $ é um Nenhuma instância}. \ End {casos} $$

Para reduzir uma instância $ i_Q $ de um problema $ \ em p $ para uma instância $ i $ de Prime, resolva $ i_q $ usando um algoritmo de tempo polinomial para $ Q $ e defina

$$ I=begin {casos} 2 & \ mbox {se $ i_q $ é uma instância sim}, \\ 1 & \ mbox {se $ i_q $ é um Nenhuma instância.} \ End {cases} $$