加载中…
2020-06-12
Traversal-invariant characterizations of logarithmic space
Siddharth BhaskarSteven LindellScott Weinstein
文献摘要
We give a novel descriptive-complexity theoretic characterization of L and NL computable queries over finite structures using traversal invariance. We summarize this as (N)L = FO + (breadth-first) traversal-invariance.
讨论
0讲解博客
生成讲解博客的中文版本
AI智能校验
生成AI智能校验的中文版本