证明保理α的问题在NP中

Question

试图阐述计算理论，但不确定解决方案：

Prove that the problem of factoring α is in NP.

我有一种感觉，这可能与发现NP问题并找到保理α的问题有关。

Answer 1

实际上这很简单。乘法在P. NP中与“并行检查所有可能的多项式大小的解决方案”相同。如果将alpha编码为长度为n bitstring，则总长度最多为n + c。

不是“ np-complete”。没有办法将任意的NP问题转变为保理。

Answer 2

p ：是一个问题，可以通过确定性的图灵机在多项式时间计算NP中的问题 ：是一个问题，通过确定性的图灵机可以非常适合多种方面。

在NP中，我们以这种方式使用了非确定性，我们只需要一个计算树的一个分支即可接受（我们在“同一”时间尝试“所有”可能性）。多项式非常容易表示，我们有一个证书（让它为c），这是对输入词的解决方案（让它为w）。证书必须为多项式长度考虑输入长度。我们的任务只是验证证书是解决方案的。例如，在SAT（令人满意的问题）中，证书是正确的分配（这是非确定性的）。

因此，您证明您的问题是在NP中：存在一个DTM，该DTM验证了一对（W，C），其中W是输入号，C是其因素。您必须只构建一个非常富裕的，使C中的因素乘以C，并将其与W进行比较。