Meu livro afirma isso
- Se um problema de decisão B estiver em P e A for reduzido para B, o problema de decisão A estará em P.
- Um problema de decisão B é NP-completo se B estiver em NP e para todo problema em A em NP, A reduz para B.
- Um problema de decisão C é NP-completo se C estiver em NP e, para algum problema NP-completo B, B se reduz a C.
Então, minhas perguntas são
- Se B ou C estiver em NP-complete, e todos os problemas no NP forem reduzidos a um problema NP-complete, usando a primeira regra, como pode qualquer problema de NP não ser NP-completo?
- Se A reduz para B, B reduz para A?
complexity-theory
np-complete
decision-problem
rubixibuc
fonte
fonte
Respostas:
Não. Para um exemplo realmente elaborado, qualquer possível problema computável A é redutível ao Problema de Interrupção: basta passar como entrada o algoritmo que resolve o problema A, mas com uma
while(true)tachinha no final após o caso verdadeiro ou falso. No entanto, sabemos que o problema da parada não é computável, portanto não pode ser reduzido a nenhum algoritmo A.A idéia básica é que, se houver uma redução de A para B, você pode aprender que B é pelo menos tão difícil de resolver quanto A e requer um algoritmo que seja pelo menos tão poderoso.
Portanto, se um problema A se reduz a um problema fácil B, podemos deduzir A é fácil (já que a redução nos fornece um algoritmo eficiente) e se um problema difícil A se reduz a um problema B, podemos deduzir que B também é difícil ( pois se B fosse fácil, então A também seria fácil). No entanto, ainda existe a possibilidade de fazer uma redução tola de um problema fácil para um problema difícil, mas neste caso não podemos deduzir nenhuma conclusão.
fonte
A primeira regra é sobre problemas em P. Não tem nada a ver com a integridade do NP. Se o problema A for NP Completo e o problema B for reduzido para A, isso não significa que B seja NP Completo.
Geralmente não, não.
fonte
Eu tenho apenas a idéia básica sobre problemas de NPC e NP. Mas tudo o que quero comentar é sobre "Se A é reduzido para B, então B é reduzido para A?"
Basta considerar um conjunto A com {2,3,4,5} elementos e o conjunto B com {3,4}. Portanto, A pode ser reduzido a B. Mas B não pode ser reduzido a A. Em vez disso, B pode ser expandido para A se B ganhar {2,5} elementos.
Mas se A e B estão tendo o mesmo. então A pode ser reduzido para B ou B pode ser reduzido para A.
fonte