1. The proof that you ``can't minimize a CFG'' starts with a reduction
   from one language to another.  What are the two languages?
   Informally, why does the reduction work?


2. How does this reduction show that you can't minimize a CFG?



3. The proof that you ``can't minimize an RE in polynomial time''
   starts with a reduction from one language to another.  What are the
   two languages?  Informally, why does the reduction work?


4. How does this reduction show that you can't minimize an RE?



5. Years ago, I was asked to create a layout system that took some
   polygons as input and placed them without overlapping into a given
   rectangle.  Show that this is NP-hard by reduction from PARTITION.


6. Suppose someone gave you a magic computer that could recognize SAT
   in polynomial time.  Given an expression, how could you determine
   the settings for the variables that worked?


7. Show that 2-SAT is in P.  I'll give you hints.