Problem Set 5
=============

Question 1 [10 points]
----------

This problem was well done.  The main problem with the
solutions was that people were vague on what to do with the
new quantifiers.  For example, they might neglect to
mentioned where the quantifiers for the new variables belong
releative to the other quantifiers.

Another problem was trying to replicate the reduction from
SAT to 3SAT, but is was not done properly.  This was more
a sign that people were being a little careless.

Question 2
2a [10 points]
2b [5  points]
----------

Most people did a good job, but there were a few people who
did not realized the difficulty in the problem.  You can
compute g(x)=y then compute f(y).  However, this is not
logspace since you cannot right down y--it is too long.  Th
is lead to low mark because they missed the main part of the
problem.

Question 3
3a [5  points]
3b [10 points]
----------

This was a difficult problems.  Most people got the main
idea, but did not implement it properly.  One common error
was in the reduction at the end was to output <G,s,s> (the
same start and end node).  This is a problem because there is
always a path from a node to itself.  Again I view this as
being careless.  I guess people were really busy at the end
of the term.