# 咩咩的完美复杂度教室

## 课程简介

在本课程里，我们讲探讨这样一个问题：

**计算机能解决什么问题？**

在本课程中，你将学到：

* 什么是语言、什么是图灵机
* 不可判定性：哪些问题是图灵机无法解决的
* 时间复杂度：能解≠能有效地解，哪些问题可以快速求解
* 电路复杂度：除了图灵机，还有其他的计算模型吗
* 概率图灵机：增加一串随机的0和1，竟然就能解决更多的问题
* 一点点密码学知识：以NIZK为例，什么样的协议被认为是安全的
  * 也许讲一下区块链里的工作量证明
* 其他（不一定讲）
  * 空间复杂度
  * 通信复杂度

### 前置知识

几乎不需要。只要了解一些集合、函数等基础概念即可（高中水平）。

## 上课方式

* 直播地址: <https://live.bleatingsheep.org/>
* 录播

## 关于我以及本课程

* bleatingsheep / b11p / 咩羊 / 咩咩
* 一般人讲东西：对自己熟悉的领域输出一些基础知识，自己实际上有更深入的理解
* 我：刚上完课就来讲了，基本上知道的也就只有讲的这些 ~~换句话说上完课我会的你就都会了~~
* 在本课程中，我会尽量使用通俗的语言进行讲解，不过于追求严谨 ~~反正我既不是数学专业也不是理论 CS 的，我也严谨不来~~

## 开课时间

### 开课列表


1. 5月19日（星期日）16:30（北京时间）

   录播: <https://www.bilibili.com/video/BV1tb421z71b/>

### 订阅课程

订阅课程后可以及时收到开课通知。

日历链接: <https://outlook.live.com/owa/calendar/00000000-0000-0000-0000-000000000000/6402f78a-8c81-4f83-91e7-f2ae343077ee/cid-D8FD15B2A646FB32/calendar.ics>

以 Outlook 为例，登录后进入日历，点“添加日历”，然后选择“从网络订阅”，粘贴链接并导入。

完成之后开启对应日历的通知功能，就可以及时收到开课提醒了！

### 课程讨论群


 ![](https://minio.outline.bleatingsheep.org/outlinefixing/uploads/8682f6d2-0f23-4aae-b075-aa3805b8ee99/d3fbbd94-4b46-49a0-8dd0-d443c4d43144/qrcode_1716104244926.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=460a9d18e7106f67%2F20261022%2Fcn-homelab-1%2Fs3%2Faws4_request&X-Amz-Date=20261022T033000Z&X-Amz-Expires=86400&X-Amz-Signature=276058bb82b3d17e8154c0a189ea33701aa8975505e47c59269fa1767b9358ec&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject " =280x498")

---

**Documents**

- [一、函数和语言](https://notes.bleatingsheep.org/s/complexity-theory/doc/5lia44cb5ye95pww5zkm6kt6kia-9vOx5Di3Qh)