P,NP P:Decision problems solvable in deterministic polynomial time NP:two definitions Decision problems solvable in nondeterministic polynomial time. Decision problems (whose valid instances are) checkable in deterministic polynomial time Let's use the second definition. Recall:A language L is just a subset of {0,1*, the set of all strings of bits. ▣{0,1*=Un2o{0,1”. 3P, NP ◼ P: Decision problems solvable in deterministic polynomial time ◼ NP: two definitions ❑ Decision problems solvable in nondeterministic polynomial time. ❑ Decision problems (whose valid instances are) checkable in deterministic polynomial time ◼ Let’s use the second definition. ◼ Recall: A language 𝐿 is just a subset of 0,1 ∗ , the set of all strings of bits. ❑ 0,1 ∗ = ڂ≤��0 0,1 𝑛 . 3