大暑 | 浅谈量子复杂性理论

文章预览

算法复杂性理论的研究基于求解问题需要消耗的资源（如时间资源、空间资源等），通过算法的复杂程度探究问题的难易程度，并建立一个按照计算难度给问题分类的体系。通常我们可以将问题规范化为二元字符串上的判定问题： 定义二元字母表   上的语言   为字母表上一些有穷序列的集合。对于一个语言   ，相应的判定问题是确定给定字符串输入   是否在语言   中。例如，我们可以定义全体质数的二进制编码的集合   ，相应的判定问题即判断给定的输入是否是质数。判定问题的另一种表述是将   对应于一系列布尔函数 （Boolean function）    ，   对应输入字符串的长度，其中当且仅当输入在语言   中时   的输出是1。 一个复杂性类包含一些难度相近的语言。例如，所有可以在多项式时间里解决的判定问题或者所有可以在多项式空间里 ………………………………