Question 1: 20 Points total
------------

Common Error 1.1: No proof was given that the language in question is in NP. -3

Common Error 1.2: Reduction does not work. Up to -10

Common Error 1.3: No argument was given that the reduction is polytime. -1

Common Error 1.4: No iff proof given to show that the reduction works. Up to -6

Common Error 1.5: When reducing from SUBSET SUM, many students did not realize 
                  that only a subset of the inputs are needed to sum to the
                  correct value, call it T to satisfy the SUBSET SUM condition,
                  whereas the language in the question required every object to 
                  be packed into bins. If the students just tried to map the
                  SUBSET SUM values directly to the objects to be packed without
                  dealing with this they were penalized up to -10.


Common Error 1.6: Reduced from 3 Partition (which is not in the notes) and did not
                  independently prove the 3 Partition is NP Complete. -4


Common Error 1.7: When reducing from Partition, some students add an extra object
                  of size 1/3 * A where A is the sum of all the values of the
                  Partition instance. This object should have had size 1/2 * A.
                  The same deduction is made if the student simply used A. -2


Common Error 1.8: Some students tried to reduce 3BPD to another NP Complete
                  language. This does not show anything. Since 3BPD is in NP,
                  we know that it reduces to any NP Complete language. This is a
                  major error as it is backwards. -15


Question 2:
------------

Common Error 2.1: FINITE-BAR also contains all strings which do not encode any 
                  Turing Machine. Therefore, any simple argument stating that
                  FINITE-BAR equals INFINITE which is undecideable had to deal
                  with this difference. Any argument which did not was
                  penalized -4. This was not an issue if you proved this with a
                  reduction.


Common Error 2.2: No iff proof given to show that the reduction works. -2



Question 3:
------------

Common Error 3.1: No dove-tailing to show that L is semi-decideable. -6

Common Error 3.2: No reduction used to show L is undecideable. -10

Common Error 3.3: When reducing from ATM, the ATM string w was not used, rather
                  the student used any string x. If <M, w> is in ATM we only know
                  how it performs on w. It may or may not halt on the other  
                  strings. If <M, w> is not in ATM, we also only know that M does
                  not halt on w and can say nothing about other strings x. This
                  makes the iff proof impossible. -6

Common Error 3.4: Dove-tailing was only done on L(M1) and not L(M2). If you run x
                  in M2 once you find that M1 halts on it and M2 never halts on x,
                  then you will never get beyond x unless you dove-tail with M2 
                  also. -3

Common Error 3.5: Some students used the line "if x in L(M1) intersect L(M2), 
                  then ... " in their answers. There is no way that you can
                  determine whether some string x is in the language of an 
                  arbitrary machine! This is ATM! Their reductions were there
                  incomputable. -10

Common Error 3.6: No iff proof given to show that the reduction works. -6

Common Error 3.7: No proof given that L is semi-decideable. -10

Common Error 3.8: Some students reductions output one machine M'. Their reductions
                  should have output a pair of machines <M1, M2>, in order to have a
                  valid input for L. -8