Marking report for Assignment 3 (Akitoshi Kawamura)
Average Mark:  45.6/50

--------------
1. (10 points)
--------------
This was simple. 

Marking scheme: 
* 5 for showing that FNC^1 contains F'NC^1. 
* 5 for showing that F'NC^1 contains FNC^1. 

--------------
2. (17 points)
--------------
For part (c), some wrote: 
    We know PATH is NL-complete, that is, PATH is the hardest problem
    in NL.  And we have shown that it's in AC^1.  So obviously NL is 
    contained in AC^1. 
But wait.  What do you mean by "PATH is NL-complete"?  It means (at
least in this course so far) that any problem A in NL can be reduced
to PATH by a logspace Turing machine.  But we have to show that A is
in AC^1 (i.e., can be computed by a log-depth unbounded-fanin
circuit), so in order to make the above argument work, you'd have to
show that this logspace TM reducing A to PATH can be replaced by a
log-depth unbounded-fanin circuit -- that is, L \subset AC^1.  (And to
show this, you probably need the argument similar to the correct
answer to the question, I think.)

Marking scheme: 
* 5 for part (a). 
* 6 for part (b). 
* 6 for part (c). 
Common reason for deduction:
[L] -3 for mixing up (or being ambiguous about) logspace reduction and
    AC^1 reduction in part (c) (see above). 

--------------
3. (11 points)
--------------
Although the hint suggests that you show that your language L
(e.g. the one defined in the sample solution) is in EXP^PH, you can
alternatively argue essentially the same way by showing that the
exponentially padded version of L is in PH.

In showing EXP^P = EXP, some wrote: 
    Because P is contained in EXP, obviously an exponential-time
    machine can, instead of querying an oracle A in P, compute A
    for itself. 
This is a mistake similar to the one that was common in the previous
assignment, where some people assumed that they can freely consult an
NL oracle in an NL algorithm.  It's true that EXP^P = EXP and NL^NL =
NL, but that's not "because" P \subset EXP (or NL \subset NL).

Marking scheme: 
If following the hint: 
* 7 for showing the existence of a language in EXP^PH that requires
  circuits of size MAX-SIZE: 
  - 3 for describing such a language; 
  - 4 for a proof that it is in EXP^PH. 
* 4 for EXP^P = EXP. 
If using padding: 
* 11 for the full proof (3 for describing an appropriate lanauge).
Common reason for deduction:
[X] -2 for misunderstanding why EXP^P = EXP (see abve). 

--------------
4. (12 points)
--------------
Apparently some people misunderstood the problem because they were not
familiar with the idea of the "smallest set that is closed under ...".

Marking scheme: 
* 5 for part (a).  A high-level sketch of the idea suffices. 
* 7 for part (b).