机构名称：
¥ 1.0
即使 P ̸ = NP 也不够。要证明单向函数存在，需要证明比 P ̸ = NP 更强的东西。更具体地说，Russell Impagliazzo [5] 有一篇关于这些关系的非常好的论文。P ̸ = NP 只意味着存在某些计算问题的困难实例（例如 3 SAT）。但要构造单向函数，我们需要提出一个对大多数输入都很难（即“平均而言很难”）的计算问题，并且我们可以有效地对其实例及其“解”进行采样。将单向函数 f 的对 ( x , f(x)) 视为解-问题对。更具体地说，将任意单向函数 f : { 0, 1 } n → { 0, 1 } m 视为输入为 n 个随机位并输出一个 m 位字符串。任务是：给定 f ( x ) 恢复 x ′ 使得 f ( x ′ ) = f ( x )。所有函数 f 都可能很容易反转为单向函数。更正式地说，对于安全参数 n 的所有选择以及所有函数 f ，可能存在一个 ppt 算法 A 使得：
未解决的问题
主要关键词
相关文件推荐
