Timeline for answer to $\mathsf{NL}$ versus $\mathsf{NL}[2]$ by Yuval Filmus
Current License: CC BY-SA 3.0
Post Revisions
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2021 at 7:21 | comment | added | Dennis | I think that what @omrib40 meant is that you provided a nondeterministic log-space TM (which guesses the state $\sigma$), but then you said that it "reads the witness tape" (which is another interpretation of NL, not using NDTM). There might be place for elaboration about how the witness is read. I think you can just keep guessing the witness (in some way, consistently with the two copies). | |
| Jun 26, 2021 at 16:11 | comment | added | Yuval Filmus | Nondeterministic computation has a verification interpretation, and also a guessing interpretation. | |
| Jun 26, 2021 at 16:09 | comment | added | BOB123 | @Yuval Filmus I couldn't fully understand the solution you suggest. especialy "The first that M does is to guess the state sigma of M'" how can M guess a state? according to the definition is a deterministic verifier, isnt it? and why is it guessing a state of M' how this helps us? furthermore, where is the witness held on? on M witness tape? | |
| Jul 26, 2017 at 14:57 | vote | accept | Don Fanucci | ||
| Jul 26, 2017 at 14:34 | history | answered | Yuval Filmus | CC BY-SA 3.0 |