2
$\begingroup$

this is a HW question, but its considered a bonus question so I'd appreciate a direction.

Definitions: enter image description here

The actual question: enter image description here

**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.

$\endgroup$
  • $\begingroup$ @YuvalFilmus You marked this as a duplicate of cs.stackexchange.com/questions/79356/mathsfnl-versus-mathsfnl2, but its not really the same question. The other question is about multiple reads of the witness tape, and my question is about a single read of the tape but with unbounded witness length. $\endgroup$ – Avital Livshits May 22 at 18:56
  • $\begingroup$ Right, sorry. The name $\mathcal{C}_2$ is not the best in these circumstances. $\endgroup$ – Yuval Filmus May 22 at 19:57
  • $\begingroup$ Please credit the source of all copied material and images. See cs.stackexchange.com/help/referencing. $\endgroup$ – D.W. May 23 at 3:26
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX). $\endgroup$ – D.W. May 23 at 3:26
  • $\begingroup$ @D.W. I tried that at first but I'm really bad at LaTex and couldnt get it right.. $\endgroup$ – Avital Livshits May 23 at 8:37
1
$\begingroup$

Let $N$ be the total number of configurations of the machine other than the witness tape, namely state, location of the input tape head, contents of the work tape, and location of the work tape head. Note that $N$ is polynomial in $n$.

We can assume without of generality that at each step, the machine reads a bit from the witness tape, and it affects its decision (we can accommodate that by adding dummy bits to the witness tape at locations where the original machine doesn't read the witness tape). The machine terminates once the witness tape runs out.

I claim that for any witness $w$, there is an equivalent witness $w'$ with $|w'| < N$. Here equivalent means that when the machine terminates, it is in the same configuration. The proof resembles that of the pumping lemma: if $|w| \geq N$, then some configuration must repeat, and so we can remove the corresponding part from the witness.

Thus, without loss of generality, the witness is of size at most $N=\operatorname{poly}(n)$. So this definition coincides with the usual definition of $\mathsf{NL}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! This clears the issue for me :) So I will just create a NTM that simulates the verifier and make a non deterministic guess every time the verifier reads from the witness tape, but after N guess it will reject. So if some x in L then from what you wrote there will be a short enough witness so that the NTM will accept. Thanks again :) $\endgroup$ – Avital Livshits May 23 at 8:33
1
$\begingroup$

$C_2 \subseteq NL$: Let $L \in C_2$. Let the log-space verifier for $L$ be $T$. We can construct a log-space NTM $T'$ which on any input simulates $T$ on the same input. Whenever $T$ tries to read the witness-tape, $T'$ just non-deterministically guesses an alphabet.

This will have the same effect as having a read-once witness tape.

| cite | improve this answer | |
$\endgroup$

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.