从素数减少

Question

我认为素数（是给定的号码是素数？）是一个很好的例子是一个决定问题。因此，当我试图解释减少时，我想举个与素数有关的问题。

如何减少到素数的决策问题，以及这些减少如何看起来像？

素数可以减少的决策问题是什么，以及这些减少如何看起来像？

Answer 1

假设您在谈论多项式时间减少，因为Prime在 $ p $ 中，您可以将其降低到任何非琐碎的决策问题（哪个至少有一个实例是答案是和至少一个实例，其中答案否）。此外，可以将<跨度类=“Math-Container”> $ P $ 中的任何问题都可以减少到Prime。

减少一个实例 $ i $ 的prime到实例 $ i_q $ 非琐碎的决定问题 $ q $ ，let $ y_q $ 和 $ n_q $ 是 $ q $ 的neS和no实例。减少如下：使用a href=“https://en.wikipedia.org/wiki/primality_test#fast_deterministic_tests”rel=“来解决 $ i $ 。 nofoloush noreferrer“> Polynomial-time algorithm 。然后，让

$$ i_q=begin {is} y_q＆\ mbox {如果$ i $是yes实例}，\\ n_q＆\ mbox {如果$ i $是a没有实例}。\结束{案例} $$

减少一个问题 $ i_q $ 问题 $ q \以p $ 为实例 $ i $ prime，解决 $ i_q $ 使用 $ q $ 并定义

$$ i=begin {suists} 2＆\ mbox {如果$ i_q $是yes实例}，\\ 1＆\ mbox {if $ i_q $是一个没有实例。} \结束{案例} $$