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!

  • 1
    $\begingroup$ This looks a lot like a question that I set as homework this week. If you are in my CS172 class, that's fine, but make sure you acknowledge any help that you receive here when you hand in your homework. $\endgroup$ Apr 17, 2016 at 15:49
  • $\begingroup$ I'm not in your class (seeing as you're from the UK and I'm not). I'm also not looking for solutions, just general help (not trying to cheat or anything). Thanks :) $\endgroup$
    – Idra
    Apr 17, 2016 at 15:58
  • $\begingroup$ No worries. If you had been in my class, I'd have no problem with you asking this question, precisely because you're only asking for help and you've actually done most of the work yourself. Best wishes for your studies! $\endgroup$ Apr 17, 2016 at 16:04

1 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)$.

  • $\begingroup$ How there could be only two transitions? $\endgroup$
    – shinzou
    May 31, 2017 at 16:47
  • $\begingroup$ Also are you creating w or reading it? where did you get it from if it's the former? $\endgroup$
    – shinzou
    May 31, 2017 at 16:49
  • $\begingroup$ If you're referring to the first part, $w$ is meant to be the witness (probably better to use a different notation to avoid confusion with the actual input), and it is given on the witness tape. Reducing the number of transitions to 2 is a simple exercise, instead of having $\delta_1,...,\delta_k$, you split into $\delta_1$ and a state from which you try out the remaining transition functions. $\endgroup$
    – Ariel
    May 31, 2017 at 19:51
  • $\begingroup$ How do you spread all the states from all the $\delta_i$s to only two? How would you handle conflicts? i.e same $Q, \Gamma$ that are mapped to different $Q, \Gamma, \{L,R\}$ $\endgroup$
    – shinzou
    May 31, 2017 at 20:24
  • $\begingroup$ You should ask this in a new question instead of creating a long discussion in the comments, but I think you have enough details to complete this yourself. I'm keeping the logic of the old transition functions, only breaking each state $q$ into $q_1,...,q_k$. The new transitions available from $q_i$ are $\delta_i$ and an epsilon transition to $q_{i+1}$. $\endgroup$
    – Ariel
    May 31, 2017 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.