0

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

Prove that the problem of factoring α is in NP.

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

4

2 回答 2

2

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

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

于 2011-01-11T00:02:28.457 回答
1

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

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

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

于 2013-04-04T08:56:16.110 回答