1. 计算的复杂性 complexity

P 类 多项式可解类

定义 P class:= 所有的 decidable 的 problem 中可以在多项式中决定的集合
即若有 $L\in P$, 那么就会存在图灵机 $M$ decides $L$, 且 $M$ 的时间复杂度是 $O(n^k)$

难以解决的问题-例: traveling salesperson problem (TSP) 旅行商问题

在一个图中，是否存在一条路径经过每个点一次且路径权值和小于常数 b ?
这个问题的求解步骤或许非常麻烦，但是当我们提出一种解之后，我们很容易就可以根据定义来进行验证其真伪，我们称这类容易验证的问题为 efficiently verifiable

其他难解决易证明问题

走迷宫问题、数独求解问题

证明属于 P 类

1. 证明属于 decidable 问题 (用伪代码定义图灵机的存在, 需要证明 correctness)
2. 证明过程可以在 $O(n^k)$ 时间内停止，这里 $n$ 表示 input size

NP 类 多项式可验证类

定义 NP class := 所有的能在多项式时间内验证一个问题的真伪，接受两个输入，$x$, $c$, 其中 x 表示一个标准 machine 问题的输入 (可能包括一些背景的设定，但是输入值是一个 设定); c 表示一个可能的解, 英文写作 certificate

证明属于 NP 类

1. 给定一个 verify-L 算法 (一个验证图灵机)
2. 证明 correctness (双向性)
   1. if $x\in L\Rightarrow \ \exists c$ s.t. $Verify(x,c)$ accept
   2. if $\exists c$ s.t. $Verify(x,c)$ accept $\Rightarrow$ $x\in L$
3. 证明时间复杂度是 $O(n^k)$