p =怎么能？ NP增强整数分解

Question

如果$ { sf p} $实际上相当于$ { sf np} $，则如何增强我们的算法以更快地将整数换成。换句话说，这一事实可以更好地理解整数分解？

Answer 1

如果$ p = np $，并且我们有一个可以解决的算法 k-sat 在多项式时间中的问题，可以简单地将整数分解简单地通过描述为K-SAT中的问题来简单地减少到K-SAT。

从本质上讲，它工作如下：您要制作一堆变量，每个变量代表$ p $，$ q $和$ n $的位。然后，您将K-SAT问题提出为$ p*q = n $。由于已知$ n $，因此您可以设置这些值。那么令人满意的作业将描述有效的$ P $和$ Q $。为了描述K-SAT中的乘法，您可以使用任何已知的乘法算法并描述其在K-SAT中的逻辑电路。有关将保理k-sat保理的更多信息，请参阅 这里.

至于更好地理解分解，这可能需要更多的研究和分析魔术算法（可以解决确定性多项式时间中的NP完整问题），也许将其专门用于K-SAT问题的整数公式（显然已经存在）一个非常特定的结构，具体取决于所使用的乘法算法）。

Answer 2

保理的决策问题是$ mathsf {np} $，并且可以在确定性的多项式时间内减少保理。

如果$ mathsf {p} = mathsf {np} $，则包括分解在内的$ mathsf {np} $中的任何问题都将具有多项式时间算法。

请注意，目前要考虑的最著名的确定性/概率算法需要指数时间，因此多项式时间算法将是一个很大的改进。为了获得一种感觉，请考虑考虑2000位数字。一个可能需要比大爆炸以来的时间更长的时间，另一个可能会以几毫秒的回答。