This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance.We define a new class of languages - VNL:all languages L s.t there exists M - a DTM with:an input-read-only tape.a witness tape which is a one-time read-only and can be read only as stay/right (the tape head cant move left).a work tape which is read/write.Also there exists p a polynomial s.t. for every w $\in \{0,1\}^*$:  $w\in L\ \iff\ \exists u\in\left\{ 0,1\right\} ^{p\left(\left|w\right|\right)}:\ M\left(w,u\right)=acc$ M is of O(log(|w|)) space complexity (where w is the input).Now we need to prove VNL=NL. I think I managed the VNL$\subseteq$NL direction:Let L$\in$VNL. then there exists M a DTM as we described before.  I then define a NDTM - $M_L$ on input w: that runs M on w,u where u is randomly generated, bit by bit, everytime M wants to move right.  It only needs to store an index to make sure u is of the right size, and that takes log(p(|w|) space, which is still logarithmic space complexity, and also running M is logarithmic. I also explain why M meets the other demands (but as they are somewhat trivial, I don't write them here to keep this post a bit shorter).I have two questions:I'm not entirely sure how to do the other direction (NL$\subseteq$VNL).  What I tried so far was: take L$\in$NL. $M_L$ is the logarithmic NDTM for it. I define M (of our new type) to treat the witness tape as a series of configurations. Somehow I'm supposed to verify its a legitimate configurations series resulting in M accepting w. Perhaps draw 2 consecutive configurations to the work tape and somehow verify the the transition between them is legitimate? Would love help with that.For another section of the question we remove the demand that the witness tape is read only to the right (which means I can read it as many times as I want). We're supposed to determine to which class VNL equals now. I thought about NP, but encountered some difficulties during the proof. Would also love help with that. Thank you!
Verifiers equivalent classes
complexity theory;space complexity