Réductions vers et depuis Prime

Question

Je pense que Prime (est le nombre donné qu'un nombre premier?) est un bon exemple de décision.Par conséquent, lorsque j'essaie d'expliquer la réduction, j'aimerais donner un exemple de problème lié à la prime.

Quels sont les problèmes de décision qui peuvent être réduits à la prime et comment ces réductions ressemblent-elles?

Quels sont les problèmes de décision que la prime peut réduire et comment ces réductions ressemblent-elles?

Answer 1

En supposant que vous parlez de réductions de temps polynomial, car la prime est dans $ p $ , vous pouvez le réduire à tout problème de décision non trivial (pour lequel Il y a au moins une instance avec réponse oui et au moins une instance avec la réponse n °). De plus, tout problème dans $ p $ peut être réduit à Prime.

Pour réduire une instance $ I $ de Prime à une instance $ i_q $ de la décision non triviale Problème $ q $ , let $ y_q $ et $ n_q $ être un oui et une instance sans instance pour $ q $ , respectivement. La réduction est la suivante: résoudre $ i $ à l'aide d'un Algorithme de temps polynomial pour Prime. Ensuite, laissez

$$ i_q=commencez {cas} y_q & \ mbox {si $ i $ i $ est une instance oui}, \\ n_q & \ mbox {si $ i $ i $ est un Aucune instance}. \ Fin {cas} $$

Réduire une instance $ i_Q $ d'un problème $ q \ in p $ à une instance $ i $ de premier, résolve $ i_q $ à l'aide d'un algorithme de temps polynomial pour $ q $ et définir

$$ i=commencements {cas} 2 & \ mbox {if $ i_q $ est une instance oui}, \\ 1 & \ mbox {Si $ i_q $ est un Aucune instance.} \ Fin {cas} $$