this is a HW question, but its considered a bonus question so I'd appreciate a direction.
**Images taken from HW in TAU Complexity course by Amnon Ta-Shma.
My thoughts on the question:
My intuition is that C2 = NL, because NSPACE(O(f(n)) ⊆ DTIME(2^O(f(n))), so for a verifier for a language in C2 as defined in the question, as it anyway runs in logarithmic space will run in polynomial time and therefore it won't be able to read more than a polynomial length witness so it doesn't add power. I already proved that the set of languages that are decided by a logspace verifier with read once witness tape and polynomial length witness are NL.
So more formally:
For Nl ⊆ C2, then for a language L that is in NL and decided by a logspace NTM M, it feels to me like I could just treat the witness as a configurations sequence that describes the choices that M did, and just check the validity of the transitions according to the delta function of M and accept only if all transitions are valid and the last configuration is accepting. This will need logarithmic space. So L in C2 (basically this is the same as bounded length witness case).
For C2 ⊆ NL: This feels harder. Denote L as a C2 language that is decided by a verifier as defined in the question. When I think about this, the verifier can read from the witness tape without writing the content to the work tape, so it could read the whole witness and still remain in the logarithmic space bound, and it would be equal to a NTM that performs |w| (length of the witness) of non deterministic choices while using logarithmic space on its work tape. Basically it means the NTM makes unbounded number of choices.
So on one hand, I don't think the definition of a NL NTM bounds the number of non-deterministic decisions (as long as the space complexity holds). So even with the arbitrary number of non deterministic choices, the complexity class is still NL because the space complexity doesn't change. But on the other hand, this means a "deeper configuration graph" and it feels like the time complexity of this NTM is greatly increasing and it doesn't feel right.
So in the case that the number of choices doesn't affect the complexity, this will mean that C2 ⊆ NL cause every time the verifier reads a character of the witness, we can make a non deterministic choice for that character and simulate the verifier.
But if this is wrong, then I'm not sure how to proceed.
I would appreciate pointing me to the correct direction, thanks!
*** Again, this is not for submission, by I would really like to solve it.