MIT 18.408 概率可验证证明 学习笔记 序

本系列是 MIT 18.408 Topics in Theoretical Computer Science: Probabilistically Checkable Proofs Fall 2022 的学习笔记。该课程内容也被用于北京理工大学 2023 春季学期的组合数学课程。

该系列全部内容均采用 CC BY-NC-SA 4.0 协议进行许可。


写这一系列笔记的直接原因当然是我这学期头铁选了我们学校开的组合数学课。

这门课其实一直都在大二下学期的培养方案里,然而因为种种原因近两年并没有实际开课过,今年也是阔别已久的恢复开课了。这门课虽然名叫组合数学,也确实涉及不少组合知识,不过其关注领域更多在理论计算机科学中的组合问题上,而非组合计数这些看上去比较「基础」的问题。

本学期研究的话题是 PCP,全称叫做概率可验证证明。对于一般的证明来说,证明的验证器会读入完整的证明,并且验证器总会就证明的正确性给出正确的判断。对于概率可验证证明,验证器只读取证明的一部分内容,对该证明正确性的判定也不一定完全准确,不过也具有一定的性质。

由于选课阶段助教已经做了预告,说明这门课的硬核性,实际选这门课的人并不算多,第一周上了两次课后又有不少人退课。

课堂笔记是这门课程的考核方式之一,每节课都会指定一个人去根据这门课所讲的内容编写相应的学习笔记。考虑到这门课包含了很多概念性的内容,还有很多陌生的数学公式和记号,结合自己数理基础并不扎实的现状,为了避免自己迷失在这些概念和符号中,还是有必要以笔记的形式理清思路,加深记忆。刚好博客很久没有更新学术性文章了,就拿这个系列充实一下博客的 timeline 吧。

由于后半学期课程压力还是比较重的,博客上的笔记内容并不会像作业的笔记任务那样非常详细,而是仅记录要点和思路,放暑假之后会尽量补全前期没有详细描述的内容。

由于前期还要完成很多别的课程的任务,再加上我也是个大鸽子,到这篇文章发出的时候,笔记已经落下了四周的进度,希望能尽快赶上吧。

所有课程笔记可以在 MIT18.408 的 Tag 下找到。

《MIT 18.408 概率可验证证明 学习笔记 序》上有2条评论

  1. 可以问一下上这门课的老师是谁么?我两年前选过这门课,那时的内容和“概率可验证证明”完全没关系啊。我记得好像就是抽屉原理、Polya定理、Möbius反演这些“看上去比较「基础」的问题”。

回复 匿名 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据