Qualquer problema em P pode ser convertido em qualquer outro problema em P em tempo polinômio?

Question

é possível converter qualquer problema em p para qualquer outro problema em p em tempo polinomial ?

Answer 1

Se por converter você significa reduzir (através de uma redução de karp), então é possível reduzir qualquer problema $ a $ em matemática $ p $ para qualquer problema não-trivial $ b $ na $ P $ .

Aqui "não trivial" significa que $ b $ tem pelo menos uma instância de Sim $ i_Y $ e pelo menos uma vez $ i_n $ (ou seja, o idioma associado à $ B $ não é < Classe Span="Recipiente de Matemática"> $ \ Fortyset $ nem $ \ sigma ^ * $ ).

Para mapear uma instância $ i_a $ de $ a $ para uma instância $ i_b $ de $ b $ simplesmente resolver $ a $ usando um algoritmo de tempo polinomial. Se $ I_A $ é uma instância sim, deixe $ i_b= i_y $ , caso contrário, deixe $ i_b= i_n $ .

Não é possível reduzir qualquer problema $ a \ in p $ para qualquer problema $ b \ in p $ . Para ver isso, deixe $ a $ ser um problema não trivial e deixe $ B $ Seja um problema trivial . Duas possíveis línguas correspondentes à $ a $ e $ B $ são $ \ {\ varepsilon \} $ e $ \ vazio $ , respectivamente.