Verifiers equivalent classes

Question

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:

1. 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.
   
2. 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!

Answer 1

To your first question, suppose your non deterministic machine has two transition functions $\delta_0,\delta_1$ (if you allow arbitrary number of transitions, then you can construct an equivalent Turing machine with only two transitions by adding more states). In that case, it is intuitive how to use the one time read witness. Read $w\in \{0,1\}^{p(|x|)}$ as a computation sequence, i.e. the $i'th$ bit is $0$ if $\delta_0$ is used and $1$ otherwise. Follow the computation described by $w$, and accept iff the original non deterministic machine accepted in this computation. I leave it to you to complete the details.

As for your second question, the class generated is indeed $NP$. Obviously $VNL\subseteq NP$, so it remains to see why $NP\subseteq VNL$. Let $L$ be some language in $NP$, so we have $L\le_p SAT$, where the reduction can be computed in logarithmic space (verify that the reduction used in the proof of Cook-Levin's theorem can indeed be computed in logspace). Let $f$ be the reduction from $L$ to $SAT$ computable in logarithmic space. Given $x\in \Sigma^*$, we would like our witness $w$ to be a satisfying assignment for $f(x)$, since we can verfiy an assignment in logarithmic space. The problem is that $|f(x)|$ is polynomial in $|x|$, so we cant write it in our work tape. You can solve this by having $f(x)$ provided in the witness (along with an assignment), and your machine could verify for all $1\le i\le |f(x)|$ that $w_i = {f(x)}_i$. Luckily, since $f$ is computable in logspace, you can verify that the witness provided the correct $f(x)$, and check if the assignment satisfies $f(x)$.