从因素到背包

Question

1. 如果有一种算法在多项式时间内通过有效检查复杂数量的每个可能因素，则可能不会使用该算法来解决无限的背包问题，因为可以将两个因素视为一个值，这是一个值，在集合中说明了集合。背包问题，另一个是第一个因素的副本数量？

   因子15; 3，5

   无界的背包，价值为15，所有整数集； {5,5,5} Andor {3,3,3,3,3}

2. 这意味着因素是np完成的吗？

3. 以这种方式解决多项式时间的无界背包问题会证明p = np吗？

Answer 1

（1）NP组件仅包含可以通过“是”或“否”回答的问题，这些问题称为决策问题。因此，即使您的减少是正确的，因子也不是NP完整的问题。实际上，如果您的减少是正确的，则证明该因素是NP-HARD。

（2）如果您想通过减少UKP（无限制的背包问题）来证明因素的NP固定性，则应该为每个实例的UKP找到一个整数$ m $（在多项式时间） $ i $的答案可以（在多项式时间）使用$ m $的分解。

在您的证明中，您只能按因子解决特定的UKP实例子集，因此这不是正确的减少。

Answer 2

如果有一种算法在多项式时间内通过有效检查复杂数的每个可能因素的算法

从这样的自相矛盾的陈述开始，您可以证明任何事情。为什么自相矛盾？

令$ n $为自然数字。 $ n $的可能因素是$ sqrt {n} $;可能有数字理论将其推迟更多，但是没有这样的结果可以消除除$ theta（ log^kn）$数字外的所有内容。因此，您必须考虑某些$ varepsilon> 0 $的$ omega（n^ varepsilon）$数字。请注意，$ n $的长度 - 输入大小！ - 是$ lceil log n rceil $。因此，您假设的算法检查了多项式时间³-不可能。

---

1. 如果有这样的结果（您可以在多项式时间列出这些候选者），那么在多项式时间内将有可能进行保理，这将是众所周知的。据我所知，问题仍然开放。
2. $ n^ varepsilon = 2^{ varepsilon log n} $
3. 假设当您说“有效”时，您的意思是“在多项式时间”。