The class P

A language L (equivalently decision problem) is in the class P if there is a polynomial time algorithm A for deciding L; Given a string x, A correctly decides if x ∈ L and running time of A on x is polynomial in |x|, the length of x. Given a context-free grammar and a string, can that string be generated by that grammar? The Class NP Nondeterministic polynomial-time Language L is in NP if there is a non-deterministic polynomial time algorithm A (Turing Machine) that decides L. For x ∈ L, A has some non-deterministic choice of moves that will make A accept x For x ∉ L, no choice of moves will make A accept