Just because a problem is decidable doesn't mean the algorithms we have for solving the problem are efficient in practice. Today we introduce the idea of efficiently decidable problems and the corresponding efficiently verifiable problems, which leads us to the biggest open question in theoretical Computer Science.
File Attachments
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.
Today's recording will be embedded on this page shortly after lecture.