单向函数与P=NP

Question

该站点包含各种单向函数的讨论及其与P和NP的关系.

其中一些讨论使用了一种语言

L=\{(x',y) ~\mid~ x'\le x \text{ and } f(x)=y \}

，其中f:\Sigma^*\to\Sigma^*是单向函数，x'\le x是前缀关系.现在的一个核心观点是，这种语言L包含在NP中，因为单词x是(x',y)\in L的“是证书”。

我不明白为何这说法是有道理的。

为什么证书x的长度在(x',y)的长度中多项式有界？

难道x在y和x'中就不可能是指数长的，但是从x来看f(x)又短又快吗？

Answer 1

是的，在您给出的语言中，x在(y,x')中是指数长的，而f是一个高效的单程函数(请注意，它只需在输入长度中以时间多项式方式运行，因此f(x)在(y,x')中不需要在时间多项式中计算)。

然而，这确实是一个小问题:您所读到的这个问题的答案只是有点不正式，只给出了证明OWF意味着P \neq NP的直觉。根据直觉，要解决这一问题，请按以下方式修改语言：

L=\{(1^n, x',y) ~\mid~ \exists x, |x| = n, x'\le x, \text{ and } f(x)=y \}，

其中1^n表示一个连续的n序列，这正好允许修复您所指出的问题(请注意，在这里x'\le x表示x'是x的前缀)。

注意:您链接到的问题的第二个答案确实提供了一个练习表的链接，其中包含了更正式的解决方案。