如何证明单向函数证明P≠NP？

Question

根据这，单向函数的存在证明了P-≠NP.这有什么证据？

证明这一点的一种方法是，如果P= NP，那么任何函数都很容易反转。P和NP是关于决策问题的，而不是计算问题。

(基本上，我的问题是关于决策问题的陈述与计算问题的关系。)

Answer 1

更容易证明P = \mathit{NP}暗示不存在单向函数：

让P = \mathit{NP}假设f是单向的.然后考虑对的L语言(x^\ast, y)，使得x^\ast是满足f(x) = y的x的前缀。L在\mathit{NP}中，因为x本身是一个见证(包括一些次要的形式细节；参见这个问题 )，我们可以用多项式时间回溯来验证这对数据，即单向函数可以在多时间内计算。

但是我们有P = \mathit{NP}，我们可以使用决定器D对L进行“倒置”y。接收输入(y, 1^n) (n是安全参数)，从对(\varepsilon, y)开始，即以空单词作为前缀，并使用D向前缀部分增量添加位，直到您用f(x) = y获得(x,y)为止。这样一种算法在多时间内运行，因为它保证了y的长度在最多的n上有一个逆图像。因此，f不是单向的，我们有矛盾.

关于决策问题和计算问题之间的关系的问题：P = \mathit{NP}困境的全部要点是回答计算一个解决方案是否像简单地验证它一样困难。这是因为非决定论实际上允许我们在计算答案时“欺骗”并避免浪费时间；我们只需猜测并检查我们的猜测是否正确。

上面陈述的一个有趣的结果是，单向函数的假设实际上比P \neq \mathit{NP}强。这与著名的密码假设层次结构(称为冲击利亚佐的五个世界 )是一致的。

Answer 2

听起来像是家庭作业问题。有一个解决方案这里。

非正式地，定义语言L={ (x'，y) s.t。x‘<= x和f(x) == y }基本上，它说x‘是x的前缀，x是y的前象。

很容易看出L在NP中，因为当给定x‘和y时，你可以在x’上附加位，直到它到达x，然后你就成功地验证了。在不确定的TM上，这只需要多项式时间。

如果P == NP，那么L在P中，这意味着，当给定x‘和y时，你可以用多项式时间判断是否有可能在x’上添加位，使x‘最终成为y的前缀。然后可以从空字符串开始，尝试追加0并进行测试，尝试追加1并进行测试，其中至少有一个将返回真，因为空字符串肯定是x的前缀。在接下来的几轮中，字符串x‘始终是x的前缀，因为您知道应该添加0还是1。最后x’将变成x。恭喜:在多项式时间内，您找到了x，它是y的前置图像。这就恢复了。