问题描述：

在学习计算机基础的时候，遇到了一些非常优美的计算机理论知识，希望大家都能来分享一些。在这里我分享一下我最喜欢的：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)。