大家都来分享点有趣的计算机知识吧
- 内容介绍
- 文章标签
- 相关推荐
在学习计算机基础的时候，遇到了一些非常优美的计算机理论知识，希望大家都能来分享一些。在这里我分享一下我最喜欢的：Levin关于单向函数的构造。
单向函数（One-Way Function）与理论计算机和密码学里的很多理论都有密切关系，诸如 NP=P 问题就跟单向函数的存在性直接相关。如果单向函数存在，那么显然 NP\neq P 。这里，有人可能有疑问：有没有可能存在单向函数，但是我们都发现不了？
Levin构造的单向函数直接终结了这个问题：要么单向函数不存在，要么我现在构造的这个函数就是一个单向函数。
背景知识
这里，我们先来看看什么是单向函数。通俗来说，单向函数就是“正向计算简单（多项式时间内可计算）、逆向计算困难（多项式时间内难计算）”。但是为了严谨，我们需要正式定义它。单向函数有两种定义，虽然看起来不同，但是实际上是等价的：
单向函数的定义
定义（强单向函数）
如果一个函数 f : \{0, 1\}^n \rightarrow \{0, 1\}^{\ell(n)} 满足以下两个条件，则称其为（强）单向函数：
- 易于计算：存在一个概率多项式时间（PPT）算法 M，使得对于所有的 x \in \{0, 1\}^*，都有 M(x) = f(x)。
- 难以求逆：\forall \text{poly}(n)，\forall PPT 敌手 A，\exists N_0，使得 \forall n > N_0 （对于足够大的 $n$），我们有
定义（弱单向函数）
与上述定义相同，除了
- 难以求逆：\exists \text{poly}(n)，\forall PPT 敌手 A，\exists N_0，使得 \forall n > N_0，我们有
强单向函数很好理解，指的是求逆成功的概率可忽略不计。而弱单向函数则指的是敌手总有一点不可忽略的概率无法求逆，由于这部分是不可忽略的，所以可以通过“并联”多个弱单向函数得到一个强单向函数，因此两者等价（由姚期智证明）。为了叙述方便，后续我们有时候会分别用到强/弱单向函数的性质，但是实际上这两者是一样的。
构造
OK，看完了背景，那么我们就来回顾一下Levin构造的单向函数，先构造以下函数：
Given\ x\in\{0,1\}^n, f_1(x)=(x',M_{I_{x'}}(x''))其中， x'=x_1|x_2|\cdots|x_{\log n} 是 x 的前 \log n 个比特， x''=x_{\log {n+1}}|x_{\log {n+2}}|\cdots|x_{n} 则是 x 剩下的比特， I_{x'} 则代表“ x' 对应的整数”， M_{I_{x'}} 则是 I_{x'} 对应的图灵机。
现在，我们来看一下这个函数的特征。当输入长度为 n 时，一共有 2^n 个 x、n 个 M_{I_{x'}} 。换言之，当我们随机选取 x\in\{0,1\}^n 并计算 f_1(x) 时，做了这么一件事：先随机选一个图灵机 M_{I_{x'}} ，再随机选一个 x'' 然后计算 M_{I_{x'}}(x'')。
如果存在单向函数的话，会得到什么结果呢？假如单向函数是存在的，那么一定有一个图灵机可以把它写下来。当 n 趋近于无穷大时，一定有至少一个 M_{I_{x'}} 就是这个单向函数！而且，由于 x' 的长度为 \log n ，所以只有 n 个不同的 M_{I_{x'}} ，也就是说这样的图灵机占 1/n 。回顾弱单向函数的定义我们可以发现，如果至少有一个 M_{I_{x'}} 是弱单向函数，而它的输出又占了整个值域的 1/n ，那么 f_1(x) 也是难于求逆的。
到这里，似乎我们已经完成了单向函数的构造。**但是，单向函数还有一个性质是易于计算。**如果我们选择的图灵机 M_{I_{x'}} 是一个超多项式时间的图灵机怎么办？这就是Levin牛逼的地方，我们遇到这样的问题肯定放弃了，但是他没有。
一个简单的思想是，我们限制一下 M_{I_{x'}} 的计算能力，让它在诸如 n^c 之内停机。但我们怎么确定 c 呢？c 不能太小，否则有可能连单向函数正向都无法完成计算。同时 c 又必须是一个常数，但在不知道单向函数的正向计算到底需要多少步的情况下，又怎么能确定 c ？Levin告诉我们，只需要将 M_{I_{x'}} 限制在 n^2 即可。换言之，如果存在单向函数，那么存在 \mathcal O(n^2) 内可计算的单向函数。 接下来，我们来证明这件事：
简略证明
给定强单向函数 g ，假设它在 m^c （这里的 m 是给 g 的输入长度 ）内可计算。令 n=m+m^c,x'=x_1|x_2|\cdots|x_{m^c} , x''=x_{m^c+1}|\cdots|x_n ，那么函数 f(x)=(x',g(x'')) 也是强单向函数。因为 $x’'$的长度为 m\approx n^{1/c} ，所以 g(x'') 的长度为 poly(n) ，这一部分仍然是难于求逆的。
同时，f 在 \mathcal O(n^2) 内可计算。因为 f 一共就三个步骤：
- 将 x 拆为 x',x'' ，可在 \mathcal O(n^2) 内完成；
- 复制 x' ，可在 \mathcal O(n^2) 内完成；
- 计算 g(x'') ，可在 m^c < n 内完成；
现在，我们只需要把 M_{I_{x'}} 的计算步骤限定在三次方内即可。换句话说，最终构造出的显式单向函数为：
f_2(x)=(x',M_{I_{x'}}'(x''))\newline M_{I_{x'}}'(x'')= \begin{cases} M_{I_{x'}}'(x'') & \text{如果在} |x''|^3 \text{内停机} \\ 0 & else \end{cases}可能表述有所不清晰，希望大佬们多包涵，也希望大家都来分享自己觉得优美、有趣的计算机基础知识！
网友解答：--【壹】--：
我对于理论计算机科学的理解仅限于证明图灵机能够打印自己 差点挂科
--【贰】--：
在学习计算机基础的时候，遇到了一些非常优美的计算机理论知识，希望大家都能来分享一些。在这里我分享一下我最喜欢的：Levin关于单向函数的构造。
单向函数（One-Way Function）与理论计算机和密码学里的很多理论都有密切关系，诸如 NP=P 问题就跟单向函数的存在性直接相关。如果单向函数存在，那么显然 NP\neq P 。这里，有人可能有疑问：有没有可能存在单向函数，但是我们都发现不了？
Levin构造的单向函数直接终结了这个问题：要么单向函数不存在，要么我现在构造的这个函数就是一个单向函数。
背景知识
这里，我们先来看看什么是单向函数。通俗来说，单向函数就是“正向计算简单（多项式时间内可计算）、逆向计算困难（多项式时间内难计算）”。但是为了严谨，我们需要正式定义它。单向函数有两种定义，虽然看起来不同，但是实际上是等价的：
单向函数的定义
定义（强单向函数）
如果一个函数 f : \{0, 1\}^n \rightarrow \{0, 1\}^{\ell(n)} 满足以下两个条件，则称其为（强）单向函数：
- 易于计算：存在一个概率多项式时间（PPT）算法 M，使得对于所有的 x \in \{0, 1\}^*，都有 M(x) = f(x)。
- 难以求逆：\forall \text{poly}(n)，\forall PPT 敌手 A，\exists N_0，使得 \forall n > N_0 （对于足够大的 $n$），我们有
定义（弱单向函数）
与上述定义相同，除了
- 难以求逆：\exists \text{poly}(n)，\forall PPT 敌手 A，\exists N_0，使得 \forall n > N_0，我们有
强单向函数很好理解，指的是求逆成功的概率可忽略不计。而弱单向函数则指的是敌手总有一点不可忽略的概率无法求逆，由于这部分是不可忽略的，所以可以通过“并联”多个弱单向函数得到一个强单向函数，因此两者等价（由姚期智证明）。为了叙述方便，后续我们有时候会分别用到强/弱单向函数的性质，但是实际上这两者是一样的。
构造
OK，看完了背景，那么我们就来回顾一下Levin构造的单向函数，先构造以下函数：
Given\ x\in\{0,1\}^n, f_1(x)=(x',M_{I_{x'}}(x''))其中， x'=x_1|x_2|\cdots|x_{\log n} 是 x 的前 \log n 个比特， x''=x_{\log {n+1}}|x_{\log {n+2}}|\cdots|x_{n} 则是 x 剩下的比特， I_{x'} 则代表“ x' 对应的整数”， M_{I_{x'}} 则是 I_{x'} 对应的图灵机。
现在，我们来看一下这个函数的特征。当输入长度为 n 时，一共有 2^n 个 x、n 个 M_{I_{x'}} 。换言之，当我们随机选取 x\in\{0,1\}^n 并计算 f_1(x) 时，做了这么一件事：先随机选一个图灵机 M_{I_{x'}} ，再随机选一个 x'' 然后计算 M_{I_{x'}}(x'')。
如果存在单向函数的话，会得到什么结果呢？假如单向函数是存在的，那么一定有一个图灵机可以把它写下来。当 n 趋近于无穷大时，一定有至少一个 M_{I_{x'}} 就是这个单向函数！而且，由于 x' 的长度为 \log n ，所以只有 n 个不同的 M_{I_{x'}} ，也就是说这样的图灵机占 1/n 。回顾弱单向函数的定义我们可以发现，如果至少有一个 M_{I_{x'}} 是弱单向函数，而它的输出又占了整个值域的 1/n ，那么 f_1(x) 也是难于求逆的。
到这里，似乎我们已经完成了单向函数的构造。**但是，单向函数还有一个性质是易于计算。**如果我们选择的图灵机 M_{I_{x'}} 是一个超多项式时间的图灵机怎么办？这就是Levin牛逼的地方，我们遇到这样的问题肯定放弃了，但是他没有。
一个简单的思想是，我们限制一下 M_{I_{x'}} 的计算能力，让它在诸如 n^c 之内停机。但我们怎么确定 c 呢？c 不能太小，否则有可能连单向函数正向都无法完成计算。同时 c 又必须是一个常数，但在不知道单向函数的正向计算到底需要多少步的情况下，又怎么能确定 c ？Levin告诉我们，只需要将 M_{I_{x'}} 限制在 n^2 即可。换言之，如果存在单向函数，那么存在 \mathcal O(n^2) 内可计算的单向函数。 接下来，我们来证明这件事：
简略证明
给定强单向函数 g ，假设它在 m^c （这里的 m 是给 g 的输入长度 ）内可计算。令 n=m+m^c,x'=x_1|x_2|\cdots|x_{m^c} , x''=x_{m^c+1}|\cdots|x_n ，那么函数 f(x)=(x',g(x'')) 也是强单向函数。因为 $x’'$的长度为 m\approx n^{1/c} ，所以 g(x'') 的长度为 poly(n) ，这一部分仍然是难于求逆的。
同时，f 在 \mathcal O(n^2) 内可计算。因为 f 一共就三个步骤：
- 将 x 拆为 x',x'' ，可在 \mathcal O(n^2) 内完成；
- 复制 x' ，可在 \mathcal O(n^2) 内完成；
- 计算 g(x'') ，可在 m^c < n 内完成；
现在，我们只需要把 M_{I_{x'}} 的计算步骤限定在三次方内即可。换句话说，最终构造出的显式单向函数为：
f_2(x)=(x',M_{I_{x'}}'(x''))\newline M_{I_{x'}}'(x'')= \begin{cases} M_{I_{x'}}'(x'') & \text{如果在} |x''|^3 \text{内停机} \\ 0 & else \end{cases}可能表述有所不清晰，希望大佬们多包涵，也希望大家都来分享自己觉得优美、有趣的计算机基础知识！
网友解答：--【壹】--：
我对于理论计算机科学的理解仅限于证明图灵机能够打印自己 差点挂科
--【贰】--：