证明因式分解问题 α处于 NP 状态
试图温习计算理论，但不确定解决方案：
Prove that the problem of factoring α is in NP.
我有一种感觉，这可能与寻找 NP 问题和找到分解 α 问题的约简有关。
Trying to brush up on computation theory but am not sure of solution to this:
Prove that the problem of factoring α is in NP.
I have a feeling it may be related to finding an NP problem and finding a reduction to the problem of factoring α.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这其实很简单。乘法在 P 中。NP 与“并行检查所有可能的多项式大小的解”相同。如果 alpha 被编码为长度为 n 的位串，则因子总长度最多为 n + c。
它不是“NP完全”。没有办法将任意 NP 问题转化为因式分解。
This is simple actually. Multiplication is in P. NP is the same as "checking all possible polynomial sized solutions in parallel". If alpha is encoded as a length n bitstring, the factors total length is at most n + c.
What it is not is "NP-complete". There is no way to turn an arbitrary NP problem into factoring.
Problem in P：是一个问题，可以通过确定性图灵机在多项式时间内计算
NP 中的问题：是一个问题，可以通过确定性图灵机进行多项式验证。
在 NP 中，我们以这样的方式使用非确定性，即我们只需要接受计算树的一个分支（我们在“同一”时间尝试“所有”可能性）。多项式非常可靠意味着我们有一个证书（假设为 c），它是输入单词（假设为 w）的解。考虑到输入长度，证书必须具有多项式长度。我们的任务只是验证证书是否是一个解决方案。例如，在 SAT（可满足性问题）中，证书是正确的分配（这是不确定性猜测的）。
所以你证明你的问题是 NP ：
存在一个验证一对 (w,c) 的 DTM，其中 w 是输入数，c 是其因子。您必须构造一个veryfier，将c 中的因子相乘并将其与w 进行比较。
Problem in P : is a problem, that is computable by Deterministic Turing Machine in polynomial time
Problem in NP : is a problem, thas is polynomicaly veryfiable by Deterministic Turing Machine.
In NP, we are using non-determinism in such way, that we require only one branch of a computation tree to be accepted (we try "all" possibilities at the "same" time). Polynomicaly veryfiable means, that we have a certificate (let it be c), that is a solution to the input word (let it be w). Certificate must be of a polynomial length considering input length. Our task is only to verify if a certificate is a solution. For example in SAT(satisfyability problem) a certificate is a correct assignement (which is guessed non-deterministically).
So You prove that your problem is in NP :
There exists a DTM that verifies a pair (w,c), where w is input number and c are its factors. You must just construct a veryfier that multiplies factors in c and compares it to w.