Riduzioni da e per primo

Question

Penso che Prime (è il numero dato un numero primo?) È un buon esempio un problema di decisione.Pertanto, quando sto cercando di spiegare la riduzione, mi piacerebbe dare un esempio di un problema correlato al primo.

Quali sono i problemi decisionali che possono essere ridotti a PRIME e come assomigliano queste riduzioni?

Quali sono i problemi di decisione che il primo può ridurre e come sono simili queste riduzioni?

Answer 1

Supponendo che tu stia parlando di riduzioni del tempo polinomiale, dal momento che Prime è in $ P $ , è possibile ridurlo a qualsiasi problema decisionale non banale (per il quale C'è almeno un esempio con risposta sì e almeno un'istanza con risposta di risposta). Inoltre, qualsiasi problema in $ p $ può essere ridotto a Prime.

Per ridurre un'istanza $ i $ del primo a un'istanza $ i_Q $ di decisione non banalizzata Problema $ Q $ , Let $ Y_Q $ e $ n_q $ Sii un sì e non è un'istanza per $ Q $ , rispettivamente. La riduzione è la seguente: Risolvi $ i $ usando un algoritmo polinomiale per primo. Quindi, lascia

$$ i_q=begin {casi} y_q & \ mbox {se $ i $ è un istanza}, \\ n_q & \ mbox {se $ i $ è a Nessuna istanza}. \ End {casi} $$

per ridurre un'istanza $ i_Q $ di un problema $ q \ in p $ a un'istanza $ i $ di Prime, risolvere $ i_Q $ utilizzando un algoritmo polinomiale per $ Q $ e Definisci

$$ i=begin {casi} 2 & \ mbox {se $ i_q $ è un istanza sì}, \\ 1 & \ mbox {se $ i_Q $ è a Nessuna istanza.} \ End {casi} $$