Logarithmic space verifier with unbounded witness

Question

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

Definitions:

The actual question:

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

Answer 1

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

Answer 2

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