Return to Colloquia & Seminar listing
An Introduction to the Theory of Computation
Student-Run Research Seminar| Speaker: | Brad Ballinger, UC Davis |
| Location: | 693 Kerr |
| Start time: | Wed, Nov 7 2001, 12:00PM |
Sometimes rather than producing an explicit solution to a problem, it is sufficient to produce an algorithm (or better, a computer program) for solving it. I will talk about a few basics from the theory of computation, including:
* The century-old question that started it all
* The definition of a Turing machine
* What is a decidable question?
* What are P and NP, and why are they important?
I plan to keep it simple, but still prove at least one big result.