2_the_class_p.md

7.2 The Class P

定义7.12（P）

$$P=\bigcup\limits_{k}$$TIME$$(n^k)$$.

$$P$$ is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine.

P的例子

定理7.14

$$PATH={<G,s,t>|G$$ is a directed graph that has a directed path from $$s$$ to $$t}$$

$$PATH\in P$$

判断有向图G中，s点到t点是否可达

定理7.16

Every context-free language is a member of P.

因此识别CFL文法的编译器parser总能在多项式时间内完成parse

证明方法：构造法