高等理论计算机 I

作者: , 共 672 字

姚期智教授给清华大学新入学研究生开的一门课,课程内容:

在经典计算复杂性方面:NP 完全性,多项式空间复杂性,对数空间复杂性,交互式证明系统,随机复杂性,去随机化,概率检验证明系统,电路复杂性,通信复杂性,判定树复杂性等。在量子计算复杂性方面将包括:量子计算模型,量子电路,量子 Fourier 变换算法, Shor 算法, Grover 量子搜索算法,量子纠错码,冯诺依曼墒等。

从这里可以看出理论计算机的一些主要的方向。按照姚先生的说法,这些是做理论的学生,多少都应该知道一点的东西,这样跟别人讨论的时候才不会 embarrass。Researcher 不应该局限于自己所专注的领域,眼界要开阔; 这也是开这门课的主要原因。

参考教材

[1] Complexity Theory: A Modern Approach, Sanjeev Arora and Boaz Barak.
[2] Quantum Computation and Quantum Information, Michael Nielsen and Isaac Chuang.
[3] Lecture nots: Quantum Computation, instructor Umesh Vazirani

这门课有 I , II 两个学期。这个学期主要讲量子计算和量子信息的一些东西吧。我恰好跟着写一些关于量子的东西放到这里,当然都是简单介绍性质的,目的是大家看了之后,对一些 NC 的东西有简单的辨别力,比如新浪科技的这篇瑞士实验显示量子信息传输速度远超光速

Q. E. D.

类似文章:
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了NP 问题一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
编程 » 算法, 算法分析
下面这个求\( 1/\sqrt{x}\) 的函数号称比直接调用 sqrt 库函数快 4 倍,来自游戏 Quake III 的源代码。