陶哲轩博客写数学问题时，通常先把对象定义清楚，再给直觉、反例和证明轮廓。把「P=NP, relativisation, and multiple choice exams」改写成可阅读的中文笔记，重点是：问题在问什么、已知到哪一步、下一步最容易走偏在哪。原站广告、分享条和导航已去掉。

问题在问什么

The most fundamental unsolved problem in complexity theory is undoubtedly the P=NP problem , which asks (roughly speaking) whether a problem which can be solved by a non-deterministic polynomial-time (NP) algorithm, can also be solved by a deterministic polynomial-time (P) algorithm. The general belief is that , i.e. there exist problems which can be solved by non-deterministic polynomial-time algorithms but not by deterministic polynomial-time algorithms.

One reason why the question is so difficult to resolve is that a certain generalisation of this question has an affirmative answer in some cases, and a negative answer in other cases. More precisely, if we give all the algorithms access to an oracle , then for one choice of this oracle, all the problems that are solvable by non-deterministic polynomial-time algorithms that calls ( ), can also be solved by a deterministic polynomial-time algorithm algorithm that calls ( ), thu

已知结果和反例

The Baker-Gill-Solovay result was quite surprising, but the idea of the proof turns out to be rather simple. To get an oracle such that , one basically sets to be a powerful simulator that can simulate non-deterministic machines (and, furthermore, can also simulate itself ); it turns out that any PSPACE-complete oracle would suffice for this task. To get an oracle for which , one has to be a bit sneakier, setting to be a query device for a sparse set of random (or high-comple

Unfortunately, the simple idea of the proof can be obscured by various technical details (e.g. using Turing machines to define and precisely), which require a certain amount of time to properly absorb. To help myself try to understand this result better, I have decided to give a sort of “allegory” of the proof, based around a (rather contrived) story about various students trying to pass a multiple choice test, which avoids all the technical details but still conveys the basi

证明或构造的主线

In this story, two students, named and (and which for sake of grammar, I will arbitrarily assume to be male), are preparing for their final exam in a maths course, which will consist of a long, tedious sequence of multiple-choice questions, or more precisely true-false questions. The exam has a reasonable but fixed time limit (e.g. three hours), and unlimited scratch paper is available during the exam. Students are allowed to bring one small index card into the exam. Other th

For each student response to a question, there are three possible outcomes:

阅读时建议盯住的点

We will assume a certain asymmetry in the grading: a few points are deducted for false negatives, but a large number of points are deducted for false positives. (There are many real-life situations in which one type of error is considered less desirable than another; for instance, when deciding on guilt in a capital crime, a false positive is generally considered a much worse mistake than a false negative.) So, while students would naturally like to ace the exam by answering

Student is hard working and careful, but unimaginative and with a poor memory. His exam strategy is to put all the techniques needed to solve the exam problems on the index card, so that they can be applied by rote during the exam. If the nature of the exam is such that can be guaranteed to ace it by this method, we say that the exam is in class . For instance, if the exam will consist of verifying various multiplication problems (e.g. “Is ?”), then this exam is in class , si

值得单独记下的条目

• Correct answer. The student answers the question correctly.
• False negative. The student answers “false”, but the actual answer is “true”.
• False positive. The student answers “true”, but the actual answer is “false”.
• is guaranteed to ace the exam if the information given to him by the proctor is reliable;
• is guaranteed not to make a false positive, even if the proctor has given him unreliable information.

阅读和落地时建议先做的 5 件事

1. 用自己的语言重写定义和结论，不看原文能不能说清对象是什么。
2. 找一个最小反例或边界情形，确认假设少一条会怎样。
3. 把证明拆成可独立检验的引理，每步只保留一个新想法。
4. 若涉及计算或形式化，先写可复现的小例子，再谈一般情形。
5. 记下尚未解决的缺口：缺估计、缺构造，还是缺正确的范畴。

和智能体、形式化工具怎么接

龙虾PRO做 OpenClaw 落地时，数学笔记最有用的部分往往是「可检验的步骤」：定义、反例、引理边界。智能体适合帮忙展开计算和检索，不适合代替你决定哪条假设能扔。

本文侧重全链路风控方法论。落地时请用自身业务单据做回放验证，不要把示例阈值直接当生产策略。 相关：风控体检 · 方案资源