证明α分解问题是NP问题

Question

试图复习计算理论，但不确定解决此问题的方法：

Prove that the problem of factoring α is in NP.

我有一种感觉，这可能与寻找NP问题和找到α分解问题的约简有关。

Answer 1

实际上，这很简单。乘法是在P.NP中实现的，NP等同于“并行检查所有可能的多项式大小的解”。如果alpha被编码为长度为n的比特串，则因子总长度至多为n+ c。

它不是"NP-complete“。没有办法将任意NP问题转化为因式分解。

Answer 2

P中的问题:是可由确定性图灵机在多项式时间中计算的问题。NP中的问题:是一个可由确定性图灵机多项式验证的问题。

在NP中，我们以这样的方式使用非确定性，即我们只需要接受计算树的一个分支(我们在“相同”的时间尝试“所有”可能性)。多项式可验证的意思是，我们有一个证书(设为c)，这是输入词的解决方案(设为w)。考虑到输入长度，证书必须是多项式长度。我们的任务只是验证证书是否是解决方案。例如，在SAT(可满足性问题)中，证书是一个正确的分配(这是不确定的猜测)。

所以你证明了你的问题在NP中:存在一个DTM，它验证一对(w，c)，其中w是输入数，c是它的因子。您只需构造一个将c中的因子相乘并将其与w进行比较的变元。