对数空间计算的模型
NL是非确定性图灵机使用O(log n)工作空间所能判定的语言类，n表示输入长度。为研究小于输入大小的空间界，模型把输入放在可反复读取但不能修改的磁带上，另设初始为空的读写工作带。空间只计工作带，不把完整输入本身计入这项预算。
非确定性表示机器可在每一步具有多个合法选择，只要存在一条接受分支，输入就被接受。它不是给分支分配概率的随机算法，也不是把所有分支占用的空间相加。空间约束限制各条分支所使用的工作存储，并保证不接受的输入没有可接受的计算路径。
不用保存整条路径
有向图可达性给定图G及顶点s、t，问是否存在从s到t的有向路径。一个NL算法从s开始，逐步猜测下一个顶点，扫描只读输入检查相应边是否存在，到达t便接受。工作带仅保存当前顶点、候选顶点及步数计数器，各需对数数量的比特。
若图有N个顶点，只需考察长度不超过N−1的简单路径；任何更长的成功行走都可删除环。因此设置有限步数上限不会漏掉可达情况。之前走过的全部顶点序列无需留下，这正是工作空间节省的来源，而不是把一条线性长度路径偷偷放在未计费的可写存储中。
为何采用对数空间归约
NL完全性要求问题本身属于NL，并且每个NL语言都能经对数空间多一归约变成它。有向可达性满足这两项条件。对任意NL机器，可把其配置作为顶点、一步合法转移作为边；机器接受，恰好等价于初始配置能够到达接受配置。
对数空间机器的配置只有多项式多个，每个配置可用对数长度编码。归约器能按需生成图的编码，不必在工作带上存下整张图。在组合归约与后续算法时，也可重新计算所需输入符号。若允许归约先任意使用多项式空间，就会掩盖研究小空间类本来要比较的资源差异。
与L、P和NP的关系
已知L⊆NL⊆P⊆NP。L是确定性对数空间类；NL包含于P，可由对多项式规模配置图执行确定性可达性搜索得到。这里用较多空间换取确定性模拟，并没有证明模拟仍只需要对数空间。L是否等于NL、NL是否等于P，仍是开放问题。
Savitch定理给出NL⊆SPACE(log² n)，但平方对数不能直接当作对数。另一方面，Immerman–Szelepcsényi定理证明NL=coNL，说明有向不可达性也可在非确定性对数空间中判定。这是额外的深刻定理，而不是把每个分支的接受、拒绝简单互换就能得到的结果。