So far in our discussion of automata, we have focused on Computability, or can a problem be solved. Today we step into the world of Complexity, or how efficiently can a problem be solved. Even though we don't know whether $\plangs = \nplangs$, we have a hunch of which problems in $\nplangs$ might not be solvable in polynomial time. Those are the $\nplangs$-complete problems, the focus of today's lecture.
File Attachments
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.