[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/certificates_based_intepretation_of_nl.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Certificates-Based Intepretation of NL" type: concept related: [Space Class L] source: https://www.jemoka.com/posts/kbhcertificates_based_intepretation_of_nl/ confidence: high status: active --- A language \(A\) is in \(NL\) if \(\exists\) a deterministic Turing Machine \(V\) that runs in logspace where \(x \in A \Leftrightarrow \exists w \in \qty {0,1}^{\text{poly}\qty(|x|)}\) (if and only if!! same as NP) such that \(V \qty(x,w) = 1\), where $x$—the real input \(x\) is on input tape one which is read-only, and the witness \(w\) is on input tape two which is read-once (because otherwise the same definition is equivalent to \(NP\)). Given this definition, STCONN is in NL is in \(\text{NL}\), witness is simply \(s\) to \(t\) path.