07 数字签名
数字签名方案的定义
06 公钥加密
寻求新的解决方案
secretary分析
到目前为止，我们对算法的分析都是基于算法在worst-case上的表现的。我们总会假设有一个adversary在已知我们设计的算法以后总会用一个最坏的输入来让我们的算法表现糟糕。然而我们发现，在某些在线算法问题下这样的分析方法太强了，以至于所有确定性算法甚至随机算法的竞争比都没有常数的竞争比，以至于worst-case分析无法比较不同算法…
01 图灵机模型
当我们提到“计算(calculation)”这个词时，指的是“回答一个数学问题”。这个数学问题可以是“求两个正整数的乘积”，“求出一个线性方程组的所有解”，“给一列数字排序”，“给定一个无向图求最大独立集的大小”等等。在计算这些问题的时候，可以有很多不同的方法。对于第一个问题，我们可以依据“乘法本质是加法”来计算， 例如我们只需做次操作；…
04 问题的难度
根据加速定理，我们明白了我们必须对算法定义复杂性而不能对问题定义复杂性。然而，直观上确实存在不同问题的难易程度(hardness)之分。有的问题只需要扫描一遍输入就可以求出，有的问题似乎除了暴力搜索之外没有好办法。那么我们应该如何比较不同问题之间的难度呢？（除非特殊说明，我们所说的“问题”就是指判定性问题，一个问题是的一个子集）
05 多项式谱系
直观上，在相同条件下最优化问题的难度高于存在性问题。判定一个解是否合法比判定该解是否是满足某最优条件的最优解要花费更多的计算资源。从逻辑刻画的角度，判定问题形如。而最优解问题形如。所以直观上，一个问题的最优化问题的难度比更难。
07 概率图灵机
许多算法中会用到随机性，这类算法称为随机算法。一个随机算法可以看作是一系列确定性算法的分布。引入随机性一般有两种目的：第一种目的是，提供一个简单的解决方案使得我们能以期望意义下更高效地完成计算，例如在快速排序中我们不通过分析数据选取一个尽可能接近中位数的pivot，而是快速地选一个随机的pivot；第二种目的是，牺牲百分之百输出正确答案这…
08 计数复杂性
离散概率本质是计数问题。所以如果想要进一步研究由概率图灵机定义的复杂性类（比如），一个很自然的角度是研究计数问题的复杂性类。
无理数的无理数次方可能是有理数
下面证明，
06 电路复杂性
在图灵机的模型下，复杂性理论的研究遇到了许多困难，至今为止许多符合直观的命题都还只是猜想而无法得到证明（比如）。于是人们意识到，造成这样的研究瓶颈的原因是“图灵机”作为模型本身太过复杂。图灵机刻画了一切计算，其使用的方法是描述若干条纸带以及读写头的移动。这样的模型明显的缺陷是其计算过程和问题本身没有结构上的对应，所以我们说图灵机的计算是“…