computation-theory - 证明分解α的问题在NP中

Question

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

Prove that the problem of factoring α is in NP.

我有一种感觉，这可能与找到一个 NP 问题并找到一个减少因子 α 的问题有关。

Answer 1

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

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

Answer 2

P中的问题：是一个问题，可以通过确定性图灵机在多项式时间内计算 NP中的问题：是一个问题，可以通过确定性图灵机进行多项式计算。

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

所以你证明你的问题出在 NP 中：存在一个验证一对 (w,c) 的 DTM，其中 w 是输入数字，c 是它的因子。您必须构造一个将 c 中的因子相乘并将其与 w 进行比较的veryfier。