5
$\begingroup$

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!

$\endgroup$
  • 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$ – David Richerby Apr 17 '16 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$ – Ungoliant Apr 17 '16 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$ – David Richerby Apr 17 '16 at 16:04
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How there could be only two transitions? $\endgroup$ – shinzou May 31 '17 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 '17 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 '17 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 '17 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 '17 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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