Reduzierungen von und von Prime

Question

Ich denke, Prime (ist die angegebene Zahl einer Primzahl?) Ist ein gutes Beispiel ein Entscheidungsproblem.Wenn ich versuche, die Reduzierung zu erklären, möchte ich ein Beispiel für ein Problem geben, das mit Prime zusammenhängt.

Was sind Entscheidungsprobleme, die auf Prime reduziert werden können, und wie sehen diese Reduktionen aus?

Was sind Entscheidungsprobleme, auf die Prime reduzieren kann, und wie sehen diese Reduzierungen aus?

Answer 1

Angenommen, Sie sprechen von mehreren Polynom-Zeit-Reduzierungen, da Prime in $ P $ ist, können Sie sie auf ein nicht triviales Entscheidungsproblem reduzieren (für das Es gibt mindestens eine Instanz mit der Antwort ja und mindestens eine Instanz mit Antwort-Nr.). Darüber hinaus kann jedes Problem in $ P $ auf Prime reduziert werden.

Um eine Instanz zu reduzieren $ I $ von Prime zu einem Instanz $ i_Q $ von nicht trivialer Entscheidung Problem $ q $ , let $ y_q $ und $ n_q $ Seien Sie ein Ja und keine Instanz für $ q $ . Die Reduktion ist wie folgt: Lösen Sie $ I $ mit einem Polynom-Zeitalgorithmus für Prime. Dann lass

$$ I_Q=beginnen {Hüllen} y_Q & \ mbox {Wenn $ i $ ein Ja-Instanz ist}, \\ n_q & \ mbox {if $ i $ ist ein Keine Instanz}. \ END {Hüllen} $$

Um eine Instanz zu reduzieren $ i_Q $ eines Problems $ q \ in P $ zu einer Instanz $ I $ von Prime, Lösen $ i_Q $ Verwenden eines Polynom-Zeit-Algorithmus für $ q $ und definieren Sie

$$ i=beginnen {hüllen} 2 & \ mbox {if $ i_q $ ist ein Ja-Instanz}, \\ 1 & \ mbox {if $ i_q $ ist ein Keine Instanz.} \ ENDE {Hüllen} $$ $$