Theory of Computation
Theory of Computation

Class 21: Reductions and Recognizability

11 April 2023

Slides from class: class21.pdf

Problem Set 9 is due on Monday, 17 April. The latex template is https://www.overleaf.com/read/mqwmbzjppfbv.

If the key opening door reduction isn’t exciting enough for you (or you’re just a fan of 1980s TV shows), you may want to watch this video: Proof by Reduction (from Fall 2020 course).

  • « Previous page: Class 20: Proving Uncomputability
  • Next page: Class 22: Rice's Theorem »

cs 3120: Theory of Computation
Spring 2023
University of Virginia
Subscribe to the  RSS feed.